More Web Proxy on the site http://driver.im/

research-article

Polynomial bounds for decoupling, with applications

Authors:

Ryan O'Donnell,

Yu ZhaoAuthors Info & Claims

CCC '16: Proceedings of the 31st Conference on Computational Complexity

Article No.: 24, Pages 1 - 18

Published: 29 May 2016 Publication History

Abstract

Let f(x) = f(x₁, ..., x_n) = Σ_|S|≤k a_S II_i∈S x_i be an n-variate real multilinear polynomial of degree at most k, where S ⊆ [n] = {1, 2, ..., n}. For its one-block decoupled version.

[EQUATION]

we show tail-bound comparisons of the form

[EQUATION]

Our constants C_k, D_k are significantly better than those known for "full decoupling". For example, when x, y, z are independent Gaussians we obtain C_k = D_k = O(k); when x, y, z are ±1 random variables we obtain C_k = O(k²), D_k = k^O(k). By contrast, for full decoupling only C_k = D_k = k^O(k) is known in these settings.

We describe consequences of these results for query complexity (related to conjectures of Aaronson and Ambainis) and for analysis of Boolean functions (including an optimal sharpening of the DFKO Inequality).

References

[1]

Scott Aaronson. Ten semi-grand challenges for quantum computing theory, 2005. http://www.scottaaronson.com/writings/qchallenge.html.

[2]

Scott Aaronson. How to solve longstanding open problems in quantum computing using only Fourier Analysis. Lecture at Banff International Research Station, 2008. http://www.scottaaronson.com/talks/openqc.ppt.

[3]

Scott Aaronson. Updated version of "ten semi-grand challenges for quantum computing theory", 2010. http://www.scottaaronson.com/blog/?p=471.

[4]

Scott Aaronson and Andris Ambainis. The need for structure in quantum speedups. Theory Of Computing, 10(6):133--166, 2014.

[5]

Scott Aaronson and Andris Ambainis. Forrelation: a problem that optimally separates quantum from classical computing. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing, pages 307--316, 2015.

Digital Library

[6]

Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, and JohnWright. Beating the random assignment on constraint satisfaction problems of bounded degree. In Proceedings of the 18th Annual International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2015.

[7]

Franck Barthe and Emanuel Milman. Transference principles for log-sobolev and spectral-gap with applications to conservative spin systems. Communications in Mathematical Physics, 323(2):575--625, 2013.

[8]

Jean Bourgain. On the distribution of the Fourier spectrum of Boolean functions. Israel Journal of Mathematics, 131(1):269--276, 2002.

[9]

Victor de la Peña. Decoupling and Khintchine's inequalities for U-statistics. Annals of Probability, 20(4):1877--1892, 1992.

[10]

Víctor de la Peña and Evarist Giné Decoupling: from dependence to independence. Springer, 1999.

[11]

Victor de la Peña and Stephen Montgomery-Smith. Decoupling inequalities for the tail probabilities of multivariate U-statistics. Annals of Probability, 23(2):806--816, 1995.

[12]

Irit Dinur. The PCP Theorem by gap amplification. Journal of the ACM, 54(3):1--44, 2007.

Digital Library

[13]

Irit Dinur, Ehud Friedgut, Guy Kindler, and Ryan O'Donnell. On the Fourier tails of bounded functions over the discrete cube. Israel Journal of Mathematics, 160(1):389--412, 2007.

[14]

David Ellis, Yuval Filmus, and Ehud Friedgut. Triangle-intersecting families of graphs. Journal of the European Mathematical Society, 14(3):841--885, 2012.

[15]

Ehud Friedgut. Boolean functions with low average sensitivity depend on few coordinates. Combinatorica, 18(1):27--36, 1998.

[16]

Ehud Friedgut and Gil Kalai. Every monotone graph property has a sharp threshold. Proceedings of the American Mathematical Society, 124(10):2993--3002, 1996.

[17]

Ehud Friedgut, Gil Kalai, and Assaf Naor. Boolean functions whose Fourier transform is concentrated on the first two levels and neutral social choice. Advances in Applied Mathematics, 29(3):427--437, 2002.

Digital Library

[18]

Evarist Giné A consequence for random polynomials of a result of de la Peña and Montgomery-Smith. In Probability in Banach Spaces 10, volume 43 of Progress in Probability. Birkhäuser--Verlag, 1998.

[19]

Jacek Jendrej, Krzysztof Oleszkiewicz, and Jakub Wojtaszczyk. On some extensions of the FKN theorem. Manuscript, 2012. To appear in Theory of Computation.

[20]

Daniel Kane. k-independent Gaussians fool polynomial threshold functions. In Proceedings of the 26th Annual Computational Complexity Conference, pages 252--261, 2011.

Digital Library

[21]

Daniel Kane and Raghu Meka. A PRG for Lipschitz functions of polynomials with applications to Sparsest Cut. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing, pages 1--10, 2013.

Digital Library

[22]

Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pages 767--775, 2002.

Digital Library

[23]

Subhash Khot and Assaf Naor. Nonembeddability theorems via Fourier analysis. Mathematische Annalen, 334(4):821--852, 2006.

[24]

Subhash Khot and Assaf Naor. Linear equations modulo 2 and the L₁ diameter of convex bodies. SIAM Journal on Computing, 38(4):1448--1463, 2008.

Digital Library

[25]

Guy Kindler. Property Testing, PCP, and juntas. PhD thesis, Tel Aviv University, 2002.

[26]

Guy Kindler and Ryan O'Donnell. Gaussian noise sensitivity and Fourier tails. In Proceedings of the 27th Annual Computational Complexity Conference, pages 137--147, 2012.

Digital Library

[27]

Guy Kindler and Shmuel Safra. Noise-resistant Boolean functions are juntas. Manuscript, 2002.

[28]

Stanisław Kwapień. Decoupling inequalities for polynomial chaos. Annals of Probability, 15(3):1062--1071, 1987.

[29]

Shachar Lovett. An elementary proof of anti-concentration of polynomials in Gaussian variables. Technical Report 182, Electronic Colloquium on Computational Complexity, 2010.

[30]

Nathaniel Macon and Abraham Spitzbart. Inverses of Vandermonde matrices. The American Mathematical Monthly, 65:95--100, 1958.

[31]

Konstantin Makarychev and Maxim Sviridenko. Solving optimization problems with diseconomies of scale via decoupling. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science, pages 571--580, 2014.

Digital Library

[32]

Elchanan Mossel, Ryan O'Donnell, and Krzysztof Oleszkiewicz. Noise stability of functions with low influences: invariance and optimality. Annals of Mathematics, 171(1):295--341, 2010.

[33]

Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014.

Digital Library

Cited By

Aaronson SAmbainis AIraids JKokainis MSmotrovs J(2016)Polynomials, quantum query complexity, and Grothendieck's inequalityProceedings of the 31st Conference on Computational Complexity10.5555/2982445.2982470(1-19)Online publication date: 29-May-2016
https://dl.acm.org/doi/10.5555/2982445.2982470

Index Terms

Polynomial bounds for decoupling, with applications
1. Mathematics of computing
  1. Discrete mathematics

Recommendations

Irrational Mixed Decomposition and Sharp Fewnomial Bounds for Tropical Polynomial Systems

Given convex polytopes $$P_1,\ldots ,P_r \subset \mathbb {R}^n$$P1, ,Pr Rn and finite subsets $$\mathcal {W}_I$$WI of the Minkowski sums $$P_I=\sum _{i \in I} P_i$$PI= i IPi, we consider the quantity $$N(\mathbf {W})=\sum _{I \subset \mathbf{[}r \mathbf{...
A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry

This paper makes two contributions towards determining some well-studied optimal constants in Fourier analysis of Boolean functions and high-dimensional geometry. It has been known since 1994 [C. Gotsman and N. Linial, Combinatorica, 14 (1994), pp. 35--50] ...
Forrelation: A Problem That Optimally Separates Quantum from Classical Computing

We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CCC '16: Proceedings of the 31st Conference on Computational Complexity

May 2016

843 pages

ISBN:9783959770088

Editor:
Ran Raz
Weizmann Institute of Science, Rehovot, Israel

Sponsors

Microsoft Reasearch: Microsoft Reasearch

Publisher

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Dagstuhl, Germany

Publication History

Published: 29 May 2016

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Aaronson SAmbainis AIraids JKokainis MSmotrovs J(2016)Polynomials, quantum query complexity, and Grothendieck's inequalityProceedings of the 31st Conference on Computational Complexity10.5555/2982445.2982470(1-19)Online publication date: 29-May-2016
https://dl.acm.org/doi/10.5555/2982445.2982470

View Options

View options

Media

Figures

Other

Tables

View Table of Contents