The correlation between parity and quadratic polynomials mod \(3\)
From MaRDI portal
Publication:1881261
DOI10.1016/j.jcss.2004.01.003zbMath1064.68043OpenAlexW2031437056MaRDI QIDQ1881261
Publication date: 4 October 2004
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2004.01.003
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (6)
Block-symmetric polynomials correlate with parity better than symmetric ⋮ Uniqueness of optimal mod 3 polynomials for parity ⋮ Estimation of certain exponential sums arising in complexity theory ⋮ Unnamed Item ⋮ Bounds on an exponential sum arising in Boolean circuit complexity ⋮ Incomplete quadratic exponential sums in several variables
Cites Work
- Unnamed Item
- A note on the power of majority gates and modular gates
- On the power of small-depth threshold circuits
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- Equations over finite fields. An elementary approach
- Exponential sums and circuits with a single threshold gate and mod-gates
- Complex polynomials and circuit lower bounds for modular counting
- On ACC
- Upper and lower bounds for some depth-3 circuit classes
- A complex-number Fourier technique for lower bounds on the mod-\(m\) degree
- The power of the middle bit of a \(\#\)P function
- On the computational power of depth 2 circuits with threshold and modulo gates
- A weight-size trade-off for circuits with MOD m gates
- Parity, circuits, and the polynomial-time hierarchy
- PP is as Hard as the Polynomial-Time Hierarchy
- On the correlation of symmetric functions
- Natural proofs
This page was built for publication: The correlation between parity and quadratic polynomials mod \(3\)
