An exact characterization of symmetric functions in \(qAC^{0}[2]\)
From MaRDI portal
Publication:5941440
DOI10.1016/S0304-3975(00)00145-6zbMath0972.68090MaRDI QIDQ5941440
No author found.
Publication date: 20 August 2001
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items
Cites Work
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Bounded-depth, polynomial-size circuits for symmetric functions
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- The complexity of symmetric functions in bounded-depth circuits
- The expressive power of voting polynomials
- Complex polynomials and circuit lower bounds for modular counting
- Parity, circuits, and the polynomial-time hierarchy
- Unnamed Item