×

Noise stability of functions with low influences: invariance and optimality. (English) Zbl 1201.60031

The motivation for this paper is the study of boolean functions \(f:\{-1,1\}^n\to\{-1,1\}\), where \(\{-1,1\}^n\) is equipped with uniform probability measure. This topic is of significant interest in theoretical computer science and it is also arises in other diverse areas of mathematics.
The authors prove an invariance principle for multilinear polynomials with low influences and bounded degree; it shows that under mild conditions, the distribution of such polynomials is essentially invariant for all product spaces. This result is one of the very few known nonlinear invariance principles. It has the advantage that its proof is simple and that its error bounds are explicit. They also show that the assumption of bounded degree can be eliminated if the polynomials are slightly “smoothed”, this extension is essential for applications to “noise stability” type problems.

MSC:

60F17 Functional limit theorems; invariance principles
60F05 Central limit and other weak theorems
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] N. Alon, I. Dinur, E. Friedgut, and B. Sudakov, ”Graph products, Fourier analysis and spectral techniques,” Geom. Funct. Anal., vol. 14, iss. 5, pp. 913-940, 2004. · Zbl 1056.05104 · doi:10.1007/s00039-004-0478-3
[2] P. Austrin, ”Balanced Max 2-Sat might not be the hardest,” in Proc. 39th Ann. ACM Symposium on Theory of Computing, Johnson, D. S. and Feige, U., Eds., New York: ACM, 2007, pp. 189-197. · Zbl 1232.68060 · doi:10.1145/1250790.1250818
[3] P. Austrin, ”Towards sharp inapproximability for any 2-CSP,” in Proc. 48th Ann. Foundations of Computer Science, Los Alamitos, CA: IEEE Computer Society, 2007, pp. 307-317. · Zbl 1206.68135 · doi:10.1137/070711670
[4] P. Austrin and E. Mossel, ”Approximation resistant predicates from pairwise independence,” in Proceedings of Conference on Computational Complexity 2008, Los Alamitos, CA: IEEE Computer Society, 2008, pp. 249-258. · Zbl 1214.68172 · doi:10.1007/s00037-009-0272-6
[5] D. Bakry, R. D. Gill, and S. A. Molchanov, Lectures on probability theory, New York: Springer-Verlag, 1994. · Zbl 0797.00021 · doi:10.1007/BFb0073871
[6] W. Beckner, ”Inequalities in Fourier analysis,” Ann. of Math., vol. 102, iss. 1, pp. 159-182, 1975. · Zbl 0338.42017 · doi:10.2307/1970980
[7] W. Beckner, ”Sobolev inequalities, the Poisson semigroup, and analysis on the sphere \(S^n\),” Proc. Nat. Acad. Science U.S.A., vol. 89, iss. 11, pp. 4816-4819, 1992. · Zbl 0766.46012 · doi:10.1073/pnas.89.11.4816
[8] M. Ben-Or and N. Linial, ”Collective coin flipping,” in Randomness and Computation, S. Micali, Ed., New York: Academic Press, 1990. · Zbl 0675.90107
[9] I. Benjamini, G. Kalai, and O. Schramm, ”Noise sensitivity of Boolean functions and applications to percolation,” Inst. Hautes Études Sci. Publ. Math., iss. 90, pp. 5-43 (2001), 1999. · Zbl 0986.60002 · doi:10.1007/BF02698830
[10] A. Bernasconi, ”Mathematical techniques for the analysis of Boolean functions,” PhD Thesis , Institute for Computational Mathematics, Pisa, 1998. · Zbl 0917.65118
[11] S. G. Bobkov, ”An isoperimetric inequality on the discrete cube, and an elementary proof of the isoperimetric inequality in Gauss space,” Ann. Probab., vol. 25, iss. 1, pp. 206-214, 1997. · Zbl 0883.60031 · doi:10.1214/aop/1024404285
[12] A. Bonami, ”Étude des coefficients de Fourier des fonctions de \(L^p(G)\),” Ann. Instit. Fourier \((\)Univ. Grenoble\()\), vol. 20, iss. fasc. 2, pp. 335-402 (1971), 1970. · Zbl 0195.42501 · doi:10.5802/aif.357
[13] C. Borell, ”Positivity improving operators and hypercontractivity,” Math. Z., vol. 180, iss. 2, pp. 225-234, 1982. · Zbl 0472.47015 · doi:10.1007/BF01318906
[14] C. Borell, ”Geometric bounds on the Ornstein-Uhlenbeck velocity process,” Z. Wahrsch. Verw. Gebiete, vol. 70, iss. 1, pp. 1-13, 1985. · Zbl 0537.60084 · doi:10.1007/BF00532234
[15] J. Bourgain, , 1999.
[16] J. Bourgain, ”On the distributions of the Fourier spectrum of Boolean functions,” Israel J. Math., vol. 131, pp. 269-276, 2002. · Zbl 1021.43004 · doi:10.1007/BF02785861
[17] J. Bourgain and G. Kalai, ”Influences of variables and threshold intervals under group symmetries,” Geom. Funct. Anal., vol. 7, iss. 3, pp. 438-461, 1997. · Zbl 0982.20004 · doi:10.1007/s000390050015
[18] A. Carbery and J. Wright, ”Distributional and \(L^q\) norm inequalities for polynomials over convex bodies in \(\mathbbR^n\),” Math. Res. Lett., vol. 8, iss. 3, pp. 233-248, 2001. · Zbl 0989.26010 · doi:10.4310/MRL.2001.v8.n3.a1
[19] S. Chatterjee, ”A simple invariance theorem,” , preprint , 2005.
[20] S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar, ”On the hardness of approximating Multicut and Sparsest-Cut,” Comput. Complexity, vol. 15, iss. 2, pp. 94-114, 2006. · Zbl 1132.68418 · doi:10.1007/s00037-006-0210-9
[21] E. de Klerk, D. V. Pasechnik, and J. P. Warners, ”On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function,” J. Comb. Optim., vol. 8, iss. 3, pp. 267-294, 2004. · Zbl 1084.68142 · doi:10.1023/B:JOCO.0000038911.67280.3f
[22] I. Dinur and E. Friedgut, ”Intersecting families are essentially contained in juntas,” , preprint , 2008. · Zbl 1243.05235 · doi:10.1017/S0963548308009309
[23] I. Dinur, E. Friedgut, G. Kindler, and R. O’Donnell, ”On the Fourier tails of bounded functions over the discrete cube,” Israel J. Math., vol. 160, pp. 389-412, 2007. · Zbl 1268.43003 · doi:10.1007/s11856-007-0068-9
[24] I. Dinur, V. Guruswami, S. Khot, and O. Regev, ”A new multilayered PCP and the hardness of hypergraph vertex cover,” SIAM J. Comput., vol. 34, iss. 5, pp. 1129-1146, 2005. · Zbl 1079.68039 · doi:10.1137/S0097539704443057
[25] I. Dinur, E. Mossel, and O. Regev, ”Conditional hardness for approximate coloring,” in Proc. 38th Annual ACM Symposium on Theory of Computing, Kleinberg, J. M., Ed., New York: ACM, 2006, pp. 344-353. · Zbl 1301.68143 · doi:10.1145/1132516.1132567
[26] I. Dinur and S. Safra, ”On the hardness of approximating minimum vertex cover,” Ann. of Math., vol. 162, iss. 1, pp. 439-485, 2005. · Zbl 1084.68051 · doi:10.4007/annals.2005.162.439
[27] R. Dobrushin, P. Groeneboom, and M. Ledoux, Lectures on probability theory and statistics, New York: Springer-Verlag, 1996. · Zbl 0855.00026 · doi:10.1007/BFb0095673
[28] G. A. Edgar, ”A noncompact Choquet theorem,” Proc. Amer. Math. Soc., vol. 49, pp. 354-358, 1975. · Zbl 0273.46012 · doi:10.2307/2040645
[29] U. Feige and G. Schechtman, ”On the optimality of the random hyperplane rounding technique for MAX CUT: Probabilistic methods in combinatorial optimization,” Random Structures Algorithms, vol. 20, iss. 3, pp. 403-440, 2002. · Zbl 1005.90052 · doi:10.1002/rsa.10036
[30] W. Feller, An introduction to probability theory and its applications, II, 2nd ed., New York: Wiley, 1971. · Zbl 0219.60003
[31] D. S. Felsenthal and M. Machover, The measurement of voting power: Theory and practice, problems and paradoxes, Cheltenham: Edward Elgar, 1998. · Zbl 0954.91019
[32] E. Friedgut, ”Boolean functions with low average sensitivity depend on few coordinates,” Combinatorica, vol. 18, iss. 1, pp. 27-35, 1998. · Zbl 0909.06008 · doi:10.1007/PL00009809
[33] E. Friedgut, ”Sharp thresholds of graph properties, and the \(k\)-sat problem,” J. Amer. Math. Soc., vol. 12, iss. 4, pp. 1017-1054, 1999. · Zbl 0932.05084 · doi:10.1090/S0894-0347-99-00305-7
[34] E. Friedgut and G. Kalai, ”Every monotone graph property has a sharp threshold,” Proc. Amer. Math. Soc., vol. 124, iss. 10, pp. 2993-3002, 1996. · Zbl 0864.05078 · doi:10.1090/S0002-9939-96-03732-X
[35] E. Friedgut, G. Kalai, and A. Naor, ”Boolean functions whose Fourier transform is concentrated on the first two levels,” Adv. in Appl. Math., vol. 29, iss. 3, pp. 427-437, 2002. · Zbl 1039.91014 · doi:10.1016/S0196-8858(02)00024-6
[36] N. G. Gamkrelidze and V. I. Rotarcprime, ”The rate of convergence in a limit theorem for quadratic forms,” Teor. Verojatnost. i Primenen., vol. 22, iss. 2, pp. 404-407, 1977. · Zbl 0385.60035 · doi:10.1137/1122045
[37] M. X. Goemans and D. P. Williamson, ”Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,” J. Assoc. Comput. Mach., vol. 42, iss. 6, pp. 1115-1145, 1995. · Zbl 0885.68088 · doi:10.1145/227683.227684
[38] F. Götze and A. N. Tikhomirov, ”Asymptotic expansions in non-central limit theorems for quadratic forms,” J. Theoret. Probab., vol. 18, iss. 4, pp. 757-811, 2005. · Zbl 1089.60017 · doi:10.1007/s10959-005-7525-3
[39] S. Janson, Gaussian Hilbert spaces, Cambridge: Cambridge Univ. Press, 1997. · Zbl 0887.60009 · doi:10.1017/CBO9780511526169
[40] J. Kahn, G. Kalai, and N. Linial, ”The influence of variables on boolean functions,” in Proc. 29th Ann. IEEE Symposium on Foundations of Computer Science, Washington, DC: IEEE Computer Society, 1988, pp. 68-80. · doi:10.1109/SFCS.1988.21923
[41] G. Kalai, ”A Fourier-theoretic perspective on the Condorcet paradox and Arrow’s theorem,” Adv. in Appl. Math., vol. 29, iss. 3, pp. 412-426, 2002. · Zbl 1038.91027 · doi:10.1016/S0196-8858(02)00023-4
[42] G. Kalai, ”Social indeterminacy,” Econometrica, vol. 72, iss. 5, pp. 1565-1581, 2004. · Zbl 1141.91373 · doi:10.1111/j.1468-0262.2004.00543.x
[43] G. Kalai and E. Friedgut, ”It Ain’t Over Till It’s Over,” , personal communication , 2006.
[44] M. L. Katz, ”Note on the Berry-Esseen theorem,” Ann. Math. Statist., vol. 34, pp. 1107-1108, 1963. · Zbl 0122.36704 · doi:10.1214/aoms/1177704037
[45] S. Khot, ”On the power of unique 2-prover 1-round games,” in Proc. 34th Ann. ACM Symposium on Theory of Computing, New York: ACM, 2002, pp. 767-775. · Zbl 1192.68367 · doi:10.1145/509907.510017
[46] S. Khot, G. Kindler, E. Mossel, and R. O’Donnell, ”Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?,” SIAM J. Comput., vol. 37, iss. 1, pp. 319-357, 2007. · Zbl 1135.68019 · doi:10.1137/S0097539705447372
[47] S. Khot and O. Regev, ”Vertex cover might be hard to approximate to within \(2-\epsilon\),” J. Comput. System Sci., vol. 74, iss. 3, pp. 335-349, 2008. · Zbl 1133.68061 · doi:10.1016/j.jcss.2007.06.019
[48] S. Khot and N. Vishnoi, ”The Unique Games Conjecture: Integrality gap for cut problems and embeddability of negative type metrics into \(\ell_1\),” in Proc. 46th Ann. Foundations of Computer Science, Los Alamitos, CA: IEEE Computer Society, 2005, pp. 53-62. · Zbl 1321.68316 · doi:10.1145/2629614
[49] G. Kindler and S. Safra, ”Noise-resistant boolean functions are juntas,” , preprint , 2003.
[50] W. Krakowiak and J. Szulga, ”Hypercontraction principle and random multilinear forms,” Probability Theory and Related Fields, vol. 77, iss. 3, pp. 325-342, 1988. · Zbl 0621.60004 · doi:10.1007/BF00319292
[51] S. Kwapień and W. A. Woyczyński, Random series and stochastic integrals: Single and multiple, Boston: Birkhäuser, 1992. · Zbl 0751.60035
[52] M. Ledoux and M. Talagrand, Probability in Banach spaces: Isoperimetry and processes, New York: Springer-Verlag, 1991. · Zbl 0748.60004
[53] J. W. Lindeberg, ”Eine neue Herleitung des Exponentialgesetzes in der Wahrscheinlichkeitsrechnung,” Math Z., vol. 15, pp. 211-225, 1922. · JFM 48.0602.04
[54] E. Mossel, ”Gaussian bounds for noise correlation of functions,” , preprint , 2008.
[55] E. Mossel, R. O’Donnell, and K. Oleszkiewicz, ”Noise stability of functions with low influences: Invariance and optimality,” in Proc. 46th Ann. Foundations of Computer Science, Los Alamitos, CA: IEEE Computer Society, 2005, pp. 21-30. · doi:10.1109/SFCS.2005.53
[56] E. Mossel, R. O’Donnell, O. Regev, J. E. Steif, and B. Sudakov, ”Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality,” Israel J. Math., vol. 154, pp. 299-336, 2006. · Zbl 1140.60007 · doi:10.1007/BF02773611
[57] R. O’Donnell and Y. Wu, ”An optimal SDP algorithm for Max-Cut, and equally optimal Long Code tests,” in Proc. 40th Ann. ACM Symposium on Theory of Computing, Ladner, R. E. and Dwork, C., Eds., New York: ACM, 2007, pp. 335-344. · Zbl 1231.68141 · doi:10.1145/1374376.1374425
[58] K. Oleszkiewicz, ”On a nonsymmetric version of the Khinchine-Kahane inequality,” in Stochastic inequalities and applications, Basel: Birkhäuser, 2003, pp. 157-168. · Zbl 1043.46017
[59] V. V. Petrov, Sums of independent random variables, New York: Springer-Verlag, 1975. · Zbl 0322.60043
[60] P. Raghvendra, ”Optimal algorithms and inapproximability results for every CSP?,” in Proc. 40th Ann. ACM Symposium on Theory of Computing, Ladner, R. E. and Dwork, C., Eds., New York: ACM, 2008, pp. 245-254. · Zbl 1231.68142 · doi:10.1145/1374376.1374414
[61] Y. Rinott and V. Rotar, ”A remark on quadrant normal probabilities in high dimensions,” Statist. Probab. Lett., vol. 51, iss. 1, pp. 47-51, 2001. · Zbl 0979.62006 · doi:10.1016/S0167-7152(00)00141-3
[62] V. I. Rotarcprime, ”Limit theorems for multilinear forms and quasipolynomial functions,” Teor. Verojatnost. i Primenen., vol. 20, iss. 3, pp. 527-546, 1975. · Zbl 0372.60030 · doi:10.1137/1120058
[63] V. I. Rotarcprime, ”Limit theorems for polylinear forms,” J. Multivariate Anal., vol. 9, iss. 4, pp. 511-530, 1979. · Zbl 0426.62013 · doi:10.1016/0047-259X(79)90055-1
[64] A. Samorodnitsky and L. Trevisan, ”Gowers uniformity, influence of variables, and PCPs,” in Proc. 38th Ann. ACM Symposium on Theory of Computing, Kleinberg, J. M., Ed., New York: ACM, 2006, pp. 11-20. · Zbl 1301.68137 · doi:10.1145/1132516.1132519
[65] W. Sheppard, ”On the application of the theory of error to cases of normal distribution and normal correlation,” Phil. Trans. Royal Soc. London, vol. 192, pp. 101-168, 1899. · JFM 30.0222.01
[66] J. Szulga, Introduction to random chaos, London: Chapman & Hall, 1998. · Zbl 1053.37028
[67] M. Talagrand, ”On Russo’s approximate zero-one law,” Annals Probab., vol. 22, iss. 3, pp. 1576-1587, 1994. · Zbl 0819.28002 · doi:10.1214/aop/1176988612
[68] M. Talagrand, ”How much are increasing sets positively correlated?,” Combinatorica, vol. 16, iss. 2, pp. 243-258, 1996. · Zbl 0861.05008 · doi:10.1007/BF01844850
[69] P. Wolff, ”Hypercontractivity of simple random variables,” Studia Math., vol. 180, iss. 3, pp. 219-236, 2007. · Zbl 1133.60011 · doi:10.4064/sm180-3-3
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.