Parity helps to compute majority
From MaRDI portal
Publication:5091774
Recommendations
- When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
- Computing majority by constant depth majority circuits with low fan-in gates
- Bounds on the Size of Small Depth Circuits for Approximating Majority
- The complexity of computing symmetric functions using threshold circuits
- Computing majority by constant depth majority circuits with low fan-in gates
Cites work
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- A complex-number Fourier technique for lower bounds on the mod-\(m\) degree
- A fixed-depth size-hierarchy theorem for AC 0 [⊕] via the coin problem
- Approximation by DNF: Examples and Counterexamples
- Bounds on the Size of Small Depth Circuits for Approximating Majority
- Certifying polynomials for \(\mathsf{AC}^0[\oplus]\) circuits, with applications to lower bounds and circuit compression
- Exponential lower bounds for depth three Boolean circuits
- Generalized Hamming weights for linear codes
- Hilbert functions and the finite degree Zariski closure in finite field combinatorial geometry
- Local list-decoding and testing of random linear codes from high error
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Near-optimal small-depth lower bounds for small distance connectivity
- Parity, circuits, and the polynomial-time hierarchy
- Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
- Representing Boolean functions as polynomials modulo composite numbers
- Separation of \(\mathrm{AC}^0[\oplus]\) formulas and circuits
- Set Systems with Restricted Cross-Intersections and the Minimum Rank ofInclusion Matrices
- Short monotone formulae for the majority function
- The expressive power of voting polynomials
- Threshold circuits of small majority-depth
Cited in
(6)- Non-interactive zero knowledge from sub-exponential DDH
- scientific article; zbMATH DE number 7087310 (Why is no real title available?)
- scientific article; zbMATH DE number 7758312 (Why is no real title available?)
- Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle?
- Optimal explicit small-depth formulas for the coin problem
- Depth-3 circuit lower bounds for k-OV
This page was built for publication: Parity helps to compute majority
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091774)
