scientific article

zbMATH Open0769.68050MaRDI QIDQ4036702FDOQ4036702

Leslie G. Valiant

Publication date: 18 May 1993

Title of this publication is not available (Why is that?)

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

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)

Cited In (30)

• Algebraic Complexity Classes
• On the reducibility of sets inside NP to sets with low information content
• 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
• On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
• Faster combinatorial algorithms for determinant and Pfaffian
• Title not available (Why is that?)
• What's hard about Boolean functional synthesis?
• Title not available (Why is that?)
• 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
• Relationships among $PL$, $\#L$, and the determinant
• The orbit problem is in the GapL hierarchy
• Title not available (Why is that?)
• The function-inversion problem: barriers and opportunities
• Characterizing Valiant's algebraic complexity classes
• Title not available (Why is that?)
• Matrix rigidity
• Compacting Boolean Formulae for Inference in Probabilistic Logic Programming
• Determinant: Old algorithms, new insights
• The complexity of the characteristic and the minimal polynomial.
• Topological bounds on the dimension of orthogonal representations of graphs
• Min-rank conjecture for log-depth circuits
• Lower Bounds for Multiplication via Network Coding
• The minrank of random graphs
• On the guessing number of shift graphs
• Decision Versus Evaluation in Algebraic Complexity

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)