Hypercontractivity for global functions and sharp thresholds. (English) Zbl 07752245
Summary: The classical hypercontractive inequality for the noise operator on the discrete cube plays a crucial role in many of the fundamental results in the analysis of Boolean functions, such as the Kahn-Kalai-Linial theorem, Friedgut’s junta theorem and the invariance principle of Mossel, O’Donnell and Oleszkiewicz [Ann. Math. (2) 171, No. 1, 295–341 (2010; Zbl 1201.60031)]. In these results the cube is equipped with the uniform (\(1/2\)-biased) measure, but it is desirable, particularly for applications to the theory of sharp thresholds, to also obtain such results for general \(p\)-biased measures. However, simple examples show that when \(p\) is small there is no hypercontractive inequality that is strong enough for such applications. In this paper, we establish an effective hypercontractivity inequality for general \(p\) that applies to ‘global functions’, i.e. functions that are not significantly affected by a restriction of a small set of coordinates. This class of functions appears naturally, e.g. in Bourgain’s sharp threshold theorem, which states that such functions exhibit a sharp threshold. We demonstrate the power of our tool by strengthening Bourgain’s theorem, making progress on two conjectures of Kahn and Kalai (both these conjectures were open when we arXived this paper in 2019 [arXiv:2103.04604]; one of them was solved in 2022; the other is still open), and proving a \(p\)-biased analogue of the seminal invariance principle of Mossel, O’Donnell, and Oleszkiewicz.
In this 2023 version of our paper we will also survey many further applications of our results that have been obtained by various authors since we arXived the first version in 2019 .
In this 2023 version of our paper we will also survey many further applications of our results that have been obtained by various authors since we arXived the first version in 2019 .
Citations:
Zbl 1201.60031References:
| [1] | Abdullah, Amirali, STOC’15-Proceedings of the 2015 ACM Symposium on Theory of Computing. A directed isoperimetric inequality with application to Bregman near neighbor lower bounds, 509-517 (2015), ACM, New York · Zbl 1321.68210 |
| [2] | Achlioptas, Dimitris, A sharp threshold for \(k\)-colorability, Random Structures Algorithms, 63-70 (1999) · Zbl 0962.05055 · doi:10.1002/(SICI)1098-2418(1999010)14:1<63::AID-RSA3>3.0.CO;2-7 |
| [3] | Ahlberg, Daniel, Noise sensitivity in continuum percolation, Israel J. Math., 847-899 (2014) · Zbl 1305.60100 · doi:10.1007/s11856-014-1038-y |
| [4] | Ahlswede, Rudolf, The diametric theorem in Hamming spaces-optimal anticodes, Adv. in Appl. Math., 429-449 (1998) · Zbl 0909.05044 · doi:10.1006/aama.1998.0588 |
| [5] | Alweiss, Ryan, Improved bounds for the sunflower lemma, Ann. of Math. (2), 795-815 (2021) · Zbl 1479.05343 · doi:10.4007/annals.2021.194.3.5 |
| [6] | Babai, L\'{a}szl\'{o}, Sidon sets in groups and induced subgraphs of Cayley graphs, European J. Combin., 101-114 (1985) · Zbl 0573.05032 · doi:10.1016/S0195-6698(85)80001-9 |
| [7] | Bafna, Mitali, STOC ’21-Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Playing unique games on certified small-set expanders, 1629-1642 ([2021] ©2021), ACM, New York · Zbl 07765275 · doi:10.1145/3406325.3451099 |
| [8] | Bafna, Mitali, Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). High dimensional expanders: eigenstripping, pseudorandomness, and unique games, 1069-1128 (2022), [Society for Industrial and Applied Mathematics (SIAM)], Philadelphia, PA · Zbl 07883628 · doi:10.1137/1.9781611977073.47 |
| [9] | Bafna, Mitali, STOC ’22-Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Hypercontractivity on high dimensional expanders, 185-194 ([2022] ©2022), ACM, New York |
| [10] | Beckner, William, Inequalities in Fourier analysis, Ann. of Math. (2), 159-182 (1975) · Zbl 0338.42017 · doi:10.2307/1970980 |
| [11] | Michael Ben-Or and Nathan Linial, Collective coin flipping, Randomness and computation, vol. 5, 1990, pp. 91-115. |
| [12] | Benjamini, Itai, Sharp threshold for percolation on expanders, Ann. Probab., 130-145 (2012) · Zbl 1239.60090 · doi:10.1214/10-AOP610 |
| [13] | Itai Benjamini and J\'er\'emie Brieussel, Noise sensitivity of random walks on groups, Preprint, 1901.03617, 2019. |
| [14] | Benjamini, Itai, Noise sensitivity of Boolean functions and applications to percolation, Inst. Hautes \'{E}tudes Sci. Publ. Math., 5-43 (2001) (1999) · Zbl 0986.60002 |
| [15] | Bhattacharyya, Arnab, 2010 IEEE 51st Annual Symposium on Foundations of Computer Science-FOCS 2010. Optimal testing of Reed-Muller codes, 488-497 (2010), IEEE Computer Soc., Los Alamitos, CA |
| [16] | Bollob\'{a}s, B., Threshold functions, Combinatorica, 35-38 (1987) · Zbl 0648.05048 · doi:10.1007/BF02579198 |
| [17] | Bonami, Aline, \'{E}tude des coefficients de Fourier des fonctions de \(L^p(G)\), Ann. Inst. Fourier (Grenoble), 335-402 (1971) (1970) · Zbl 0195.42501 |
| [18] | Borell, Christer, Geometric bounds on the Ornstein-Uhlenbeck velocity process, Z. Wahrsch. Verw. Gebiete, 1-13 (1985) · Zbl 0537.60084 · doi:10.1007/BF00532234 |
| [19] | Bourgain, J., Influences of variables and threshold intervals under group symmetries, Geom. Funct. Anal., 438-461 (1997) · Zbl 0982.20004 · doi:10.1007/s000390050015 |
| [20] | Dinur, Irit, Intersecting families are essentially contained in juntas, Combin. Probab. Comput., 107-122 (2009) · Zbl 1243.05235 · doi:10.1017/S0963548308009309 |
| [21] | Dinur, Irit, Independent sets in graph powers are almost contained in juntas, Geom. Funct. Anal., 77-97 (2008) · Zbl 1147.05058 · doi:10.1007/s00039-008-0651-1 |
| [22] | Eberhard, Sean, Product mixing in the alternating group, Discrete Anal., Paper No. 2, 19 pp. (2016) · Zbl 1454.20020 · doi:10.19086/da.610 |
| [23] | Efron, B., The jackknife estimate of variance, Ann. Statist., 586-596 (1981) · Zbl 0481.62035 |
| [24] | David Ellis, Guy Kindler, and Noam Lifshitz, An analogue of Bonami’s lemma for functions on spaces of linear maps, and 2-2 games, Preprint, 2209.04243, 2022. |
| [25] | Yuval Filmus, Guy Kindler, Noam Lifshitz, and Dor Minzer, Hypercontractivity on the symmetric group, Preprint, 2009.05503, 2020. |
| [26] | Frankl, Peter, The Erd\H{o}s-Ko-Rado theorem for integer sequences, Combinatorica, 55-63 (1999) · Zbl 0959.05115 · doi:10.1007/s004930050045 |
| [27] | Frankston, Keith, Thresholds versus fractional expectation-thresholds, Ann. of Math. (2), 475-495 (2021) · Zbl 1472.05132 · doi:10.4007/annals.2021.194.2.2 |
| [28] | Friedgut, Ehud, Boolean functions with low average sensitivity depend on few coordinates, Combinatorica, 27-35 (1998) · Zbl 0909.06008 · doi:10.1007/PL00009809 |
| [29] | Friedgut, Ehud, Sharp thresholds of graph properties, and the \(k\)-sat problem, J. Amer. Math. Soc., 1017-1054 (1999) · Zbl 0932.05084 · doi:10.1090/S0894-0347-99-00305-7 |
| [30] | Friedgut, Ehud, A sharp threshold for van der Waerden’s theorem in random subsets, Discrete Anal., Paper No. 7, 20 pp. (2016) · Zbl 1346.05270 · doi:10.19086/da.615 |
| [31] | Friedgut, Ehud, Every monotone graph property has a sharp threshold, Proc. Amer. Math. Soc., 2993-3002 (1996) · Zbl 0864.05078 · doi:10.1090/S0002-9939-96-03732-X |
| [32] | F\"{u}redi, Zolt\'{a}n, Exact solution of the hypergraph Tur\'{a}n problem for \(k\)-uniform linear paths, Combinatorica, 299-322 (2014) · Zbl 1324.05192 · doi:10.1007/s00493-014-2838-4 |
| [33] | Fusco, N., The sharp quantitative isoperimetric inequality, Ann. of Math. (2), 941-980 (2008) · Zbl 1187.52009 · doi:10.4007/annals.2008.168.941 |
| [34] | Gowers, W. T., Quasirandom groups, Combin. Probab. Comput., 363-387 (2008) · Zbl 1191.20016 · doi:10.1017/S0963548307008826 |
| [35] | Gross, Leonard, Logarithmic Sobolev inequalities, Amer. J. Math., 1061-1083 (1975) · Zbl 0318.46049 · doi:10.2307/2373688 |
| [36] | Gur, Tom, STOC ’22-Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Hypercontractivity on high dimensional expanders, 176-184 ([2022] ©2022), ACM, New York |
| [37] | Haramaty, Elad, Optimal testing of multivariate polynomials over small prime fields, SIAM J. Comput., 536-562 (2013) · Zbl 1275.68068 · doi:10.1137/120879257 |
| [38] | Hatami, Hamed, A structure theorem for Boolean functions with small total influences, Ann. of Math. (2), 509-533 (2012) · Zbl 1253.05128 · doi:10.4007/annals.2012.176.1.9 |
| [39] | Huang, Hao, The size of a hypergraph and its matching number, Combin. Probab. Comput., 442-450 (2012) · Zbl 1242.05268 · doi:10.1017/S096354831100068X |
| [40] | Vishesh Jain and Huy Tuan Pham, Optimal thresholds for Latin squares, Steiner triple systems, and edge colorings, Preprint, 2212.06109, 2022. |
| [41] | Johansson, Anders, Factors in random graphs, Random Structures Algorithms, 1-28 (2008) · Zbl 1146.05040 · doi:10.1002/rsa.20224 |
| [42] | Kahn, Jeff, Thresholds and expectation thresholds, Combin. Probab. Comput., 495-502 (2007) · Zbl 1118.05093 · doi:10.1017/S0963548307008474 |
| [43] | Jeff Kahn, Gil Kalai, and Nathan Linial, The influence of variables on Boolean functions, 29th Annual Symposium on Foundations of Computer Science, IEEE, 1988, pp. 68-80. |
| [44] | Kaufman, Tali, 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science-FOCS 2022. Improved optimal testing results from global hypercontractivity, 98-109 ([2022] ©2022), IEEE Computer Soc., Los Alamitos, CA · Zbl 1508.68011 |
| [45] | Peter Keevash, The optimal edge-colouring threshold, Preprint, 2212.04397, 2022. |
| [46] | Peter Keevash, Noam Lifshitz, Eoin Long, and Dor Minzer, Sharp thresholds and expanded hypergraphs, 2019. |
| [47] | Peter Keevash, Noam Lifshitz, Eoin Long, and Dor Minzer, Forbidden intersections for codes, Preprint, 2103.05050, 2021. |
| [48] | Peter Keevash, Noam Lifshitz, and Dor Minzer, On the largest product-free subsets of the alternating groups, arXiv preprint 2205.15191, 2022. |
| [49] | Keevash, Peter, Stability for vertex isoperimetry in the cube, J. Combin. Theory Ser. B, 113-144 (2020) · Zbl 1448.05199 · doi:10.1016/j.jctb.2020.04.009 |
| [50] | Keevash, Peter, A stability result for the cube edge isoperimetric inequality, J. Combin. Theory Ser. A, 360-375 (2018) · Zbl 1377.05193 · doi:10.1016/j.jcta.2017.11.005 |
| [51] | Keller, Nathan, The junta method for hypergraphs and the Erd\H{o}s-Chv\'{a}tal simplex conjecture, Adv. Math., Paper No. 107991, 95 pp. (2021) · Zbl 1476.05146 · doi:10.1016/j.aim.2021.107991 |
| [52] | Keller, Nathan, Approximation of biased Boolean functions of small total influence by DNFs, Bull. Lond. Math. Soc., 667-679 (2018) · Zbl 1394.05138 · doi:10.1112/blms.12167 |
| [53] | Subhash Khot, Dor Minzer, Dana Moshkovitz, and Muli Safra, Small set expansion in the Johnson graph, Electronic Colloquium on Computational Complexity (ECCC), 2018. · Zbl 1429.68077 |
| [54] | Khot, Subhash, 59th Annual IEEE Symposium on Foundations of Computer Science-FOCS 2018. Pseudorandom sets in Grassmann graph have near-perfect expansion, 592-601 (2018), IEEE Computer Soc., Los Alamitos, CA · Zbl 1405.68005 · doi:10.1109/FOCS.2018.00062 |
| [55] | Kudekar, Shrinivas, Reed-Muller codes achieve capacity on erasure channels, IEEE Trans. Inform. Theory, 4298-4316 (2017) · Zbl 1370.94389 · doi:10.1109/TIT.2017.2673829 |
| [56] | Lifshitz, Noam, Hypergraph removal lemmas via robust sharp threshold theorems, Discrete Anal., Paper No. 11, 46 pp. (2020) · Zbl 1450.05061 · doi:10.19086/da |
| [57] | Lubetzky, Eyal, Strong noise sensitivity and random graphs, Ann. Probab., 3239-3278 (2015) · Zbl 1339.82005 · doi:10.1214/14-AOP959 |
| [58] | G. Margulis, Probabilistic characteristic of graphs with large connectivity, Problems Info. Transmission, Plenum Press, 1977. |
| [59] | Mehta, Madan Lal, Random matrices, Pure and Applied Mathematics (Amsterdam), xviii+688 pp. (2004), Elsevier/Academic Press, Amsterdam · Zbl 1107.15019 |
| [60] | Montgomery, Richard, Spanning trees in random graphs, Adv. Math., 106793, 92 pp. (2019) · Zbl 1421.05080 · doi:10.1016/j.aim.2019.106793 |
| [61] | Mossel, Elchanan, Gaussian bounds for noise correlation of functions, Geom. Funct. Anal., 1713-1756 (2010) · Zbl 1205.60051 · doi:10.1007/s00039-010-0047-x |
| [62] | Mossel, Elchanan, Robust optimality of Gaussian noise stability, J. Eur. Math. Soc. (JEMS), 433-482 (2015) · Zbl 1384.60062 · doi:10.4171/JEMS/507 |
| [63] | Mossel, Elchanan, Noise stability of functions with low influences: invariance and optimality, Ann. of Math. (2), 295-341 (2010) · Zbl 1201.60031 · doi:10.4007/annals.2010.171.295 |
| [64] | O’Donnell, Ryan, Analysis of Boolean functions, xx+423 pp. (2014), Cambridge University Press, New York · Zbl 1336.94096 · doi:10.1017/CBO9781139814782 |
| [65] | Park, Jinyoung, 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science-FOCS 2022. A proof of the Kahn-Kalai conjecture, 636-639 ([2022] ©2022), IEEE Computer Soc., Los Alamitos, CA · Zbl 1508.68011 |
| [66] | Przykucki, Micha\l Vertex-isoperimetric stability in the hypercube, J. Combin. Theory Ser. A, 105186, 19 pp. (2020) · Zbl 1433.05169 · doi:10.1016/j.jcta.2019.105186 |
| [67] | Russo, Lucio, An approximate zero-one law, Z. Wahrsch. Verw. Gebiete, 129-139 (1982) · Zbl 0501.60043 · doi:10.1007/BF00537230 |
| [68] | Schramm, Oded, Quantitative noise sensitivity and exceptional times for percolation, Ann. of Math. (2), 619-672 (2010) · Zbl 1213.60160 · doi:10.4007/annals.2010.171.619 |
| [69] | Smirnov, Stanislav, XIVth International Congress on Mathematical Physics. Critical percolation and conformal invariance, 99-112 (2005), World Sci. Publ., Hackensack, NJ · Zbl 1221.82055 |
| [70] | Talagrand, Michel, On Russo’s approximate zero-one law, Ann. Probab., 1576-1587 (1994) · Zbl 0819.28002 |
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.
