Block-symmetric polynomials correlate with parity better than symmetric

DOI10.1007/s00037-017-0153-3zbMath1379.68153OpenAlexW1473667869MaRDI 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

zbMATH Keywords

correlationsymmetrydegreepolynomialparity

Mathematics Subject Classification ID

Symmetric functions and generalizations (05E05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Products of ideals and jet schemes

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

This page was built for publication: Block-symmetric polynomials correlate with parity better than symmetric