Parity helps to compute majority
From MaRDI portal
Publication:5091774
DOI10.4230/LIPIcs.CCC.2019.23OpenAlexW2947443956MaRDI QIDQ5091774
Igor C. Oliveira, Rahul Santhanam, Srikanth Srinivasan
Publication date: 27 July 2022
Full work available at URL: https://doi.org/10.4230/LIPIcs.CCC.2019.23
Related Items (4)
Unnamed Item ⋮ Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? ⋮ Unnamed Item ⋮ Non-interactive zero knowledge from sub-exponential DDH
Cites Work
- Unnamed Item
- Unnamed Item
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Threshold circuits of small majority-depth
- The expressive power of voting polynomials
- Representing Boolean functions as polynomials modulo composite numbers
- Exponential lower bounds for depth three Boolean circuits
- A complex-number Fourier technique for lower bounds on the mod-\(m\) degree
- 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
- Short monotone formulae for the majority function
- Parity, circuits, and the polynomial-time hierarchy
- Bounds on the Size of Small Depth Circuits for Approximating Majority
- Generalized Hamming weights for linear codes
- Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
- A fixed-depth size-hierarchy theorem for AC 0 [⊕ via the coin problem]
- Set Systems with Restricted Cross-Intersections and the Minimum Rank ofInclusion Matrices
- Near-optimal small-depth lower bounds for small distance connectivity
- Approximation by DNF: Examples and Counterexamples
This page was built for publication: Parity helps to compute majority
