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
Estimates on exponential sums (11L07) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
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\)
