Polynomial bounds for decoupling, with applications

DOI10.4230/LIPIcs.CCC.2016.24zbMath1380.68231arXiv1512.01603OpenAlexW2963631284MaRDI QIDQ5368758

Ryan O'Donnell, Yu Zhao

Publication date: 10 October 2017

Full work available at URL: https://arxiv.org/abs/1512.01603

zbMATH Keywords

Fourier analysisBoolean functionsdecouplingquery complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial probability (60C05)

Related Items

Forrelation: A Problem That Optimally Separates Quantum from Classical Computing ⋮ Decoupling inequalities with exponential constants ⋮ On the Fourier spectrum of functions on Boolean cubes ⋮ Unifying presampling via concentration bounds ⋮ Polynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors