Some results on uniform arithmetic circuit complexity

DOI10.1007/BF01195199zbMath0799.68084MaRDI QIDQ4285623

David A. Mix Barrington, Mark Valence, Gudmund Skovbjerg Frandsen

Publication date: 13 November 1994

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Related Items (1)

On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits

Cites Work

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

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