Real advantage

DOI10.1145/2540089MaRDI QIDQ2947588zbMATH OpenOpenAlexFDO

Authors Emanuele Viola, Alexander Razborov

Publication date 24 September 2015

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2540089

zbMATH Keywords

correlation boundslower boundsparitypolynomials

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On the degree of Boolean functions as real polynomials
• On the Correlation Between Parity and Modular Polynomials
• The correlation between parity and quadratic polynomials mod \(3\)
• On the correlation of symmetric functions
• Uniqueness of optimal mod 3 polynomials for parity

Cited in

(12)

• Geometric and o-minimal Littlewood-Offord problems
• Anti-concentration of polynomials: dimension-free covariance bounds and decay of Fourier coefficients
• Subdeterminant maximization via nonconvex relaxations and anti-concentration
• Anti-concentration Inequalities for Polynomials
• Learning Your Comparative Advantages
• On polynomial approximations to \(\mathrm{AC}^0\)
• Combinatorial anti-concentration inequalities, with applications
• Anticoncentration for subgraph statistics
• An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs
• Anticoncentration and Berry-Esseen bounds for random tensors
• The edge-statistics conjecture for hypergraphs
• Resolution of the quadratic Littlewood-Offord problem

This page was built for publication: Real advantage

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947588)