Bounded-depth, polynomial-size circuits for symmetric functions
From MaRDI portal
Publication:1063574
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
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
