scientific article

zbMath0769.68050MaRDI QIDQ4036702

Leslie G. Valiant

Publication date: 18 May 1993

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

Boolean modelarithmetic circuitsBoolean circuitscircuit sizelow-level complexityarithmetic modelSamuelson-Berkowitz method for computing the determinant

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Guessing games on triangle-free graphs ⋮ The combinatorial approach yields an NC algorithm for computing Pfaffians ⋮ Compacting Boolean Formulae for Inference in Probabilistic Logic Programming ⋮ Determinant: Old algorithms, new insights ⋮ Faster combinatorial algorithms for determinant and Pfaffian ⋮ The function-inversion problem: barriers and opportunities ⋮ The complexity of the characteristic and the minimal polynomial. ⋮ The orbit problem is in the GapL hierarchy ⋮ The Orbit Problem Is in the GapL Hierarchy ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Min-rank conjecture for log-depth circuits ⋮ Relationships among $PL$, $\#L$, and the determinant ⋮ Matrix rigidity ⋮ The minrank of random graphs ⋮ Characterizing Valiant's algebraic complexity classes ⋮ On the reducibility of sets inside NP to sets with low information content ⋮ On the complexity of matrix rank and rigidity ⋮ Algebraic Complexity Classes ⋮ Lower Bounds for Multiplication via Network Coding ⋮ On the guessing number of shift graphs ⋮ Non-commutative arithmetic circuits: depth reduction and size lower bounds ⋮ On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits ⋮ Topological bounds on the dimension of orthogonal representations of graphs