On the fourier tails of bounded functions over the discrete cube

DOI10.1145/1132516.1132580zbMath1301.43008OpenAlexW2115180773MaRDI QIDQ2931406

Ryan O'Donnell, Guy Kindler, Ehud Friedgut, Irit Dinur

Publication date: 25 November 2014

Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

Fourier analysisBoolean functionssymmetry-breaking

Mathematics Subject Classification ID

Combinatorial probability (60C05) Harmonic analysis on specific compact groups (43A75) Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42A38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

Forrelation: A Problem That Optimally Separates Quantum from Classical Computing ⋮ On the impossibility of key agreements from quantum random oracles ⋮ Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions ⋮ Unifying presampling via concentration bounds ⋮ On set systems without a simplex-cluster and the junta method ⋮ Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas

This page was built for publication: On the fourier tails of bounded functions over the discrete cube