When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
From MaRDI portal
Publication:1346613
DOI10.1007/BF01263420zbMath0829.68058MaRDI QIDQ1346613
Publication date: 6 April 1995
Published in: Computational Complexity (Search for Journal in Brave)
Related Items (13)
Upper and lower bounds for some depth-3 circuit classes ⋮ Exponential lower bound for bounded depth circuits with few threshold gates ⋮ Learning $$AC^0$$ Under k-Dependent Distributions ⋮ New algorithms and lower bounds for circuits with linear threshold gates ⋮ Learning intersections of halfspaces with a margin ⋮ NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth ⋮ The communication complexity of addition ⋮ Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates ⋮ Threshold circuits of small majority-depth ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Circuits over PP and PL ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression ⋮ Agnostically Learning Boolean Functions with Finite Polynomial Representation
Cites Work
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
- Random oracles separate PSPACE from the polynomial-time hierarchy
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
- The expressive power of voting polynomials
- Depth reduction for circuits of unbounded fan-in
- Approximating threshold circuits by rational functions
- On ACC
- Some connections between bounded query classes and non-uniform complexity.
- PP is closed under intersection
- PP is closed under truth-table reductions
- Rational approximation to \(|x|\)
This page was built for publication: When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
