An exact characterization of symmetric functions in \(qAC^{0}[2]\)

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)

zbMATH Keywords

symmetric functionlower boundcircuit complexityperiodparity function

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

On the Probabilistic Degrees of Symmetric Boolean Functions

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