Block-symmetric polynomials correlate with parity better than symmetric
From MaRDI portal
Publication:2410677
DOI10.1007/s00037-017-0153-3zbMath1379.68153MaRDI QIDQ2410677
Emanuele Viola, Daniel Kreymer, Frederic Green
Publication date: 18 October 2017
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-017-0153-3
05E05: Symmetric functions and generalizations
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Estimation of certain exponential sums arising in complexity theory
- Incomplete quadratic exponential sums in several variables
- Uniqueness of optimal mod 3 polynomials for parity
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- Exponential sums and circuits with a single threshold gate and mod-gates
- The correlation between parity and quadratic polynomials mod \(3\)
- Symmetric polynomials over \(\mathbb Z_{m}\) and simultaneous communication protocols
- Bounds on an exponential sum arising in Boolean circuit complexity
- On the Power of Small-Depth Computation
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- On the correlation of symmetric functions
- Natural proofs