Some results on uniform arithmetic circuit complexity

DOI10.1007/BF01195199MaRDI QIDQ4285623zbMATH OpenFDO

Authors Mark Valence, David A. Mix Barrington, Gudmund S. Frandsen

Publication date 13 November 1994

Published in Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01195199

zbMATH Keywords

arithmetic expressionscomplexity class AEpolynomial-size unbounded fan-in arithmetic circuits

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Finite fields and commutative rings (number-theoretic aspects) (11T99) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• An arithmetic model of computation equivalent to threshold circuits
• On uniformity within \(NC^ 1\)
• scientific article; zbMATH DE number 1161568
• Mathematical Foundations of Computer Science 2003
• Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two

Cites work

• A complexity theory based on Boolean algebra
• An arithmetic model of computation equivalent to threshold circuits
• Constant Depth Reducibility
• Expressibility and Parallel Complexity
• Factor Refinement
• Factorization of Symmetric Matrices and Trace-Orthogonal Bases in Finite Fields
• Finding Isomorphisms Between Finite Fields
• scientific article; zbMATH DE number 3882549 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 3385535 (Why is no real title available?)
• Languages that Capture Complexity Classes
• Matrix Factorization over GF(2) and Trace-Orthogonal Bases of GF(2ⁿ )
• New Algorithms for Finding Irreducible Polynomials Over Finite Fields
• On Relating Time and Space to Size and Depth
• On the Number of Self-Dual Bases of GF(q m ) Over GF(q)
• On uniform circuit complexity
• On uniformity within \(NC^ 1\)
• P-uniform circuit complexity
• Parity, circuits, and the polynomial-time hierarchy
• Self-Complementary Normal Bases in Finite Fields
• The computational efficacy of finite-field arithmetic

Cited in

(8)

• An arithmetic model of computation equivalent to threshold circuits
• On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
• Uniform proofs of ACC representations
• P-uniform circuit complexity
• Extensional Uniformity for Boolean Circuits
• Functions definable by arithmetic circuits
• scientific article; zbMATH DE number 1148334 (Why is no real title available?)
• On uniformity and circuit lower bounds

This page was built for publication: Some results on uniform arithmetic circuit complexity

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