Bounded depth arithmetic circuits: Counting and closure

DOI10.1007/3-540-48523-6_12MaRDI QIDQ4938621zbMATH OpenFDO

Authors David A. Mix Barrington, Samir Datta, Huong Lêthanh, Eric Allender, Andris Ambainis

Publication date 25 April 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://scholarworks.umass.edu/cs_faculty_pubs/88

zbMATH Keywords

arithmetic circuitscircuit complexity classespath countingthreshold circuits

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Applications of graph theory to circuits and networks (94C15)

Recommendations

• On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
• Semantical counting circuits
• Mathematical Foundations of Computer Science 2003

Cited in

(18)

• Circuits in bounded arithmetic. I
• Semantical counting circuits
• On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• On the complexity of matrix rank and rigidity
• On the power of algebraic branching programs of width two
• On the power of algebraic branching programs of width two
• Functions definable by arithmetic circuits
• Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
• Resource trade-offs in syntactically multilinear arithmetic circuits
• On counting AC^0 circuits with negative constants
• Semantical counting circuits
• Model-theoretic characterization of Boolean and arithmetic circuit classes of small depth
• The limits of depth reduction for arithmetic formulas
• Descriptive complexity of \#AC\(^0\) functions
• Mathematical Foundations of Computer Science 2003
• scientific article; zbMATH DE number 2196509 (Why is no real title available?)
• Parameterised counting in logspace

This page was built for publication: Bounded depth arithmetic circuits: Counting and closure

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