Bounded-depth, polynomial-size circuits for symmetric functions

DOI10.1016/0304-3975(85)90045-3zbMath0574.94024OpenAlexW2063584607MaRDI QIDQ1063574

Maria M. Klawe, Ronald Fagin, Nicholas J. Pippenger, Larry J. Stockmeyer

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90045-3

zbMATH Keywords

spectrumgrowth ratesymmetric Boolean functionsmajority functionsmeasure functionparity functions

Mathematics Subject Classification ID

Related Items

Uniform constant-depth threshold circuits for division and iterated multiplication., Threshold circuits of bounded depth, Generalized lower bounds derived from Hastad's main lemma, The complexity of symmetric functions in bounded-depth circuits, Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\), Construction of universal enumerators and formulas for threshold functions, Properties of symmetric Boolean functions, Reversal complexity revisited, Linear-size constant-depth polylog-threshold circuits, Separating complexity classes related to \(\Omega\)-decision trees, An exact characterization of symmetric functions in \(qAC^{0}[2\)], First-order expressibility of languages with neutral letters or: The Crane Beach conjecture, On the Probabilistic Degrees of Symmetric Boolean Functions, Threshold circuits of small majority-depth, On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits, Languages defined with modular counting quantifiers, Non-uniform automata over groups, On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology

Cites Work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Constant Depth Reducibility
• Unnamed Item
• Unnamed Item