Block-symmetric polynomials correlate with parity better than symmetric

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

zbMATH Keywords

correlation; symmetry; degree; polynomial; parity

Mathematics Subject Classification ID

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

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