Some results on uniform arithmetic circuit complexity
From MaRDI portal
Publication:4285623
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)
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)
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