scientific article; zbMATH DE number 176871

MaRDI QIDQ4036702zbMATH OpenFDO

Authors Leslie G. Valiant

Publication date 18 May 1993

zbMATH Keywords

arithmetic circuitsBoolean circuitsBoolean modelcircuit sizelow-level complexityarithmetic modelSamuelson-Berkowitz method for computing the determinant

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1775437
• Lower bounds for unrestricted Boolean circuits: open problems
• scientific article; zbMATH DE number 1161568
• Circuit complexity and multiplicative complexity of Boolean functions
• Non-cancellative Boolean circuits: A generalization of monotone boolean circuits

Cited in

(31)

• Decision Versus Evaluation in Algebraic Complexity
• On the reducibility of sets inside NP to sets with low information content
• Non-cancellative Boolean circuits: a generalization of monotone Boolean circuits
• On minrank and forbidden subgraphs
• The Orbit Problem Is in the GapL Hierarchy
• Semirings for probabilistic and neuro-symbolic logic programming
• Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
• Guessing games on triangle-free graphs
• Faster combinatorial algorithms for determinant and Pfaffian
• On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
• scientific article; zbMATH DE number 1775437 (Why is no real title available?)
• What's hard about Boolean functional synthesis?
• Compacting Boolean formulae for inference in probabilistic logic programming
• On the complexity of matrix rank and rigidity
• The combinatorial approach yields an NC algorithm for computing Pfaffians
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• The orbit problem is in the GapL hierarchy
• Relationships among $PL$, $\#L$, and the determinant
• scientific article; zbMATH DE number 1559536 (Why is no real title available?)
• The function-inversion problem: barriers and opportunities
• Characterizing Valiant's algebraic complexity classes
• Matrix rigidity
• Algebraic complexity classes
• The complexity of the characteristic and the minimal polynomial.
• Determinant: Old algorithms, new insights
• Min-rank conjecture for log-depth circuits
• On minrank and the Lovász theta-function
• Topological bounds on the dimension of orthogonal representations of graphs
• The minrank of random graphs
• Lower Bounds for Multiplication via Network Coding
• On the guessing number of shift graphs

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4036702)