×

Boolean function analysis on high-dimensional expanders. (English) Zbl 07857944

Summary: We initiate the study of Boolean function analysis on high-dimensional expanders. We give a random-walk based definition of high-dimensional expansion, which coincides with the earlier definition in terms of two-sided link expanders. Using this definition, we describe an analog of the Fourier expansion and the Fourier levels of the Boolean hypercube for simplicial complexes. Our analog is a decomposition into approximate eigenspaces of random walks associated with the simplicial complexes. Our random walk definition and the decomposition have the additional advantage that they extend to the more general setting of posets, encompassing both high-dimensional expanders and the Grassmann poset, which appears in recent work on the unique games conjecture. We then use this decomposition to extend the Friedgut-Kalai-Naor theorem to high-dimensional expanders. Our results demonstrate that a constant-degree high dimensional expander can sometimes serve as a sparse model for the Boolean slice or hypercube, and quite possibly additional results from Boolean function analysis can be carried over to this sparse model. Therefore, this model can be viewed as a derandomization of the Boolean slice, containing only \(\vert \chi(k - 1)\vert = O(n)\) points in contrast to \(\binom{n}{k}\) points in the \((k)\)-slice (which consists of all \(n\)-bit strings with exactly \(k\) ones).

MSC:

05C48 Expander graphs

References:

[1] Abdolazimi, D., Liu, K., Oveis-Gharan, S.: A matrix trickle-down theorem on simplicial complexes and applications to sampling colorings. In: Nelson, J. (ed.) Proceedings of 63rd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 161-172. (2022). doi:10.1109/FOCS52979
[2] Alev, V.L., Jeronimo, F.G., Tulsiani, M.: Approximating constraint satisfaction problems on high-dimensional expanders. In: Zuckerman, D. (ed.) Proceedings of 60th IEEE Symposium on Foundations of Computer Science (FOCS), pp 180-201. (2019). doi:10.1109/FOCS.2019
[3] Anari, N., Liu, K., Oveis-Gharan, S., Vinzant, C.: Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid. In: Charikar , M., and Cohen, E. (eds.) Proceedings of 51st ACM Symposium on Theory of Computing (STOC), pp. 1-12. (2019). doi:10.1145/3313276.3316385 · Zbl 1433.68606
[4] Anari, N.; Liu, K.; Oveis-Gharan, S., Spectral independence in high-dimensional expanders and applications to the hardcore model, SIAM J. Comput., 2020 · Zbl 1522.05449 · doi:10.1137/20M1367696
[5] Bafna, M., Hopkins, M., Kaufman, T., Lovett, S.: Hypercontractivity on high dimensional expanders. In: Leonardi, S., Gupta, A. (eds.) Proceedings of 54th ACM Symposium on Theory of Computing (STOC), pp. 185-194. (2022). doi:10.1145/3519935.3520040 · Zbl 07774331
[6] Barak, B.; Gopalan, P.; Håstad, J.; Meka, R.; Raghavendra, P.; Steurer, D., Making the long code shorter, SIAM J. Comput., 44, 5, 1287-1324, 2015 · Zbl 1330.68089 · doi:10.1137/130929394
[7] Barak, B., Kothari, P., Steurer, D.: Small-set expansion in shortcode graph and the 2-to-2 conjecture. In: Blum, A. (ed.) Proceedings of 10th Innovations in Theoretical Computer Science (ITCS), vol. 124 of LIPIcs, pp. 9:1-9:12. Schloss Dagstuhl (2019). doi:10.4230/LIPIcs.ITCS.2019.9 · Zbl 1518.68136
[8] Brouwer, AE; Cohen, AM; Neumaier, A., Distance-Regular Graphs, 1989, Berlin: Springer, Berlin · Zbl 0747.05073 · doi:10.1007/978-3-642-74341-2
[9] Chen, Z., Galanis, A., Stefankovic, D., Vigoda, E.: Rapid mixing for colorings via spectral independence. In: Marx, D. (ed.) Proceedings of 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1548-1557 (2021). doi:10.1137/1.9781611976465.94 · Zbl 07788432
[10] Chen, Z., Liu, K., Vigoda, E.: Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion. In Khuller , S., Williams, V.V. (eds.) Proceedings of 53rd ACM Symposium on Theory of Computing (STOC), pp. 1537-1550. (2021). doi:10.1145/3406325.3451035 · Zbl 07765268
[11] Chen, Z.; Liu, K.; Vigoda, E., Rapid mixing of Glauber dynamics up to uniqueness via contraction, SIAM J. Comput., 52, 1, 196-237, 2023 · Zbl 07672228 · doi:10.1137/20M136685X
[12] Ching, W.; Li, W., Ramanujan hypergraphs, Geom. Funct. Anal., 14, 2, 380-399, 2004 · Zbl 1084.05047 · doi:10.1007/s00039-004-0461-z
[13] Dikstein, Y., Dinur, I., Filmus, Y., Harsha, P.: Boolean function analysis on high-dimensional expanders. In: Blais, E., Jansen, K., Rolim, J.D.P., Steurer, D. (eds.) Proceedings of 22nd International Conference on Randomization and Computation (RANDOM), vol. 116 of LIPIcs, pp. 38:1-38:20. Schloss Dagstuhl (2018). doi:10.4230/LIPIcs.APPROX-RANDOM.2018.38 · Zbl 1522.68739
[14] Dikstein, Y., Dinur, I.: Agreement testing theorems on layered set systems. In: Zuckerman, D. (ed.) Proceedings of 60th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 1495-1524. (2019). doi:10.1109/FOCS.2019.00088
[15] Dinur, I., Kaufman, T.: High dimensional expanders imply agreement expanders. In: Umans, C. (ed.) Proceedings of 58th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 974-985 (2017). doi:10.1109/FOCS.2017.94
[16] Dinur, I., Khot, S., Kindler, G., Minzer, D., Safra, M.: On non-optimally expanding sets in Grassmann graphs. In: Diakonikolas, I., Kempe, D., Henzinger, M. (eds.) Proceedings of 50th ACM Symposium on Theory of Computing (STOC), pp. 940-951 (2018). doi:10.1145/3188745.3188806 · Zbl 1429.68077
[17] Dinur, I., Khot, S., Kindler, G., Minzer, D., Safra, M.: Towards a proof of the 2-to-1 games conjecture? In: Diakonikolas, I., Kempe, D., Henzinger, M. (eds.) Proceedings of 50th ACM Symposium on Theory of Computing (STOC), pp. 376-389 (2018). doi:10.1145/3188745.3188804 · Zbl 1429.68076
[18] Dinur, I., Filmus, Y., Harsha, P.: Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests. In: Chan, T.M. (ed.) Proceedings of 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2124-2133 (2019). doi:10.1137/1.9781611975482.128 · Zbl 1432.68349
[19] Dinur, I.; Harsha, P.; Kaufman, T.; Navon, IL; TaShma, A., List decoding with double samplers, SIAM J. Comput., 50, 2, 301-349, 2021 · Zbl 1518.94147 · doi:10.1137/19M1276650
[20] Dotterrer, D.; Kaufman, T.; Wagner, U., On expansion and topological overlap, Geometriae Dedicata, 195, 307-317, 2018 · Zbl 1393.05315 · doi:10.1007/s10711-017-0291-4
[21] Dunkl, C., A Krawtchouk polynomial addition theorem and wreath products of symmetric groups, Indiana Univ. Math. J., 25, 335-358, 1976 · Zbl 0326.33008 · doi:10.1512/iumj.1976.25.25030
[22] Ellis, D.; Filmus, Y.; Friedgut, E., A quasi-stability result for dictatorships in \({S}_n\), Combinatorica, 35, 5, 573-618, 2015 · Zbl 1389.05167 · doi:10.1007/s00493-014-3027-1
[23] Ellis, D.; Filmus, Y.; Friedgut, E., A stability result for balanced dictatorships in \({S}_n\), Random Struct. Algorithm., 46, 3, 494-530, 2015 · Zbl 1342.94135 · doi:10.1002/rsa.20515
[24] Ellis, D., Filmus, Y., Friedgut, E.: Low degree Boolean functions on \({S}_n\), with an application to isoperimetry. Forum Math. Sigma 5:e23 (2017). doi:10.1017/fms.2017.24 · Zbl 1384.05149
[25] Evra, S., Finite quotients of Bruhat-Tits buildings as geometric expanders, J. Topol. Anal., 09, 1, 51-66, 2017 · Zbl 1358.05075 · doi:10.1142/S1793525317500078
[26] Evra, S., Kaufman, T.: Bounded degree cosystolic expanders of every dimension. In: Proceeding of 48th ACM Symposium on Theory of Computing (STOC), pp. 36-48 (2016). doi:10.1145/2897518.2897543 · Zbl 1376.05095
[27] Feng, W., Guo, H., Yin, Y., Zhang, C.: Rapid mixing from spectral independence beyond the Boolean domain. ACM Trans. Algorithm. 18(3), 28:1-28:32 (2022). doi:10.1145/3531008 · Zbl 07758422
[28] Filmus, Y., An orthogonal basis for functions over a slice of the Boolean hypercube, Electron. J. Comb., 23, 1, 23, 2016 · Zbl 1330.05163
[29] Filmus, Y., Friedgut-Kalai-Naor theorem for slices of the Boolean cube, Chic. J. Theoret. Comput. Sci., 14, 2016, 2016 · Zbl 1401.06014 · doi:10.4086/cjtcs.2016.014
[30] Filmus, Y.; Mossel, E., Harmonicity and invariance on slices of the Boolean cube, Probab. Theory Relat. Fields, 175, 721-782, 2019 · Zbl 1423.60059 · doi:10.1007/s00440-019-00900-w
[31] Filmus, Y., Kindler, G., Mossel, E., Wimmer, K.: Invariance principle on the slice. ACM Trans. Comput. Theory 10(3), 11:1-11:37 (2018). doi:10.1145/3186590 · Zbl 1427.60018
[32] Fox, J.; Gromov, M.; Lafforgue, V.; Naor, A.; Pach, J., Overlap properties of geometric expanders, J. Reine Angew. Math., 2012, 671, 49-83, 2012 · Zbl 1306.05171 · doi:10.1515/crelle.2011.157
[33] Friedgut, E.; Kalai, G.; Naor, A., Boolean functions whose Fourier transform is concentrated on the first two levels and neutral social choice, Adv. Appl. Math., 29, 3, 427-437, 2002 · Zbl 1039.91014 · doi:10.1016/S0196-8858(02)00024-6
[34] Garland, H., \(p\)-adic curvature and the cohomology of discrete subgroups of \(p\)-adic groups, Ann. Math., 97, 3, 375-423, 1973 · Zbl 0262.22010 · doi:10.2307/1970829
[35] Gromov, M., Singularities, expanders and topology of maps. Part 2 from combinatorics to topology via algebraic isoperimetry, Geom. Funct. Anal., 20, 416-526, 2010 · Zbl 1251.05039 · doi:10.1007/s00039-010-0073-8
[36] Gur, T., Lifshitz, N., Liu, S.: STOC 2022. In: Leonardi, S., Gupta, A. (eds.) In: Proceedings of 54th ACM Symposium on Theory of Computing (STOC), pp. 176-184 (2022). doi:10.1145/3519935.3520004
[37] Kaufman, T., Lubotzky, A.: High dimensional expanders and property testing. In: Naor, M. (ed.) Proceedings of 5th Innovations in Theoretical Computer Science (ITCS), pp. 501-506. ACM (2014). doi:10.1145/2554797.2554842 · Zbl 1365.68462
[38] Kaufman, T., Mass, D.: Good distance lattices from high dimensional expanders (2018). arXiv:1803.02849
[39] Kaufman, T.; Oppenheim, I., High order random walks: beyond spectral gap, Combinatorica, 40, 1, 245-281, 2020 · Zbl 1463.05543 · doi:10.1007/s00493-019-3847-0
[40] Kaufman, T.; Kazhdan, D.; Lubotzky, A., Isoperimetric inequalities for Ramanujan complexes and topological expanders, Geom. Funct. Anal., 26, 1, 250-287, 2016 · Zbl 1339.05075 · doi:10.1007/s00039-016-0362-y
[41] Khot, S., Minzer, D., Safra, D.: On independent sets, 2-to-2 games, and Grassmann graphs. In: Hatami, H., McKenzie, P., King, V. (eds.) Proceedings of 49th ACM Symposium on Theory of Computing (STOC), pp. 576-589 (2017). doi:10.1145/3055399.3055432 · Zbl 1370.68130
[42] Khot, S., Minzer, D., Safra, M.: Pseudorandom sets in Grassmann graph have near-perfect expansion. In: Thorup, M. (ed.) Proceedings of 59th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 592-601 (2018). doi:10.1109/FOCS.2018.00062
[43] Linial, N.; Meshulam, R., Homological connectivity of random 2-complexes, Combinatorica, 26, 4, 475-487, 2006 · Zbl 1121.55013 · doi:10.1007/s00493-006-0027-9
[44] Lubotzky, A.; Phillips, R.; Sarnak, P., Ramanujan graphs, Combinatorica, 8, 3, 261-277, 1988 · Zbl 0661.05035 · doi:10.1007/BF02126799
[45] Lubotzky, A.; Samuels, B.; Vishne, U., Explicit constructions of Ramanujan complexes of type \(\tilde{A_d} \), Eur. J. Comb., 26, 6, 965-993, 2005 · Zbl 1135.05038 · doi:10.1016/j.ejc.2004.06.007
[46] Lubotzky, A.; Samuels, B.; Vishne, U., Ramanujan complexes of type \(\tilde{A_d} \), Isr. J. Math., 149, 1, 267-299, 2005 · Zbl 1087.05036 · doi:10.1007/BF02772543
[47] Montanaro, A.; Osborne, T., Quantum Boolean functions, Chic. J. Theoret. Comput. Sci., 2010 · Zbl 1286.68161 · doi:10.4086/cjtcs.2010.001
[48] Moshkovitz, D.; Raz, R., Sub-constant error low degree test of almost-linear size, SIAM J. Comput., 38, 1, 140-180, 2008 · Zbl 1165.68029 · doi:10.1137/060656838
[49] O’Donnell, R.; Wimmer, K., KKL, Kruskal-Katona, and monotone nets, SIAM J. Comput., 42, 6, 2375-2399, 2013 · Zbl 1285.68075 · doi:10.1137/100787325
[50] Oppenheim, I., Local spectral expansion approach to high dimensional expanders part I: descent of spectral gaps, Discret. Comput. Geom., 59, 2, 293-330, 2018 · Zbl 1383.05312 · doi:10.1007/s00454-017-9948-x
[51] Plaza, R.: Variations on differential posets. In: Stanton, D. (ed.) Invariant Theory and Tableaux, IMA Vol. Math. Appl., vol. 19, pp. 145-165. Springer, Berlin (1990) · Zbl 0707.06001
[52] Plaza, R., Stability for intersecting families in \({PGL}(2, q)\), Electron. J. Comb., 22, 4, P4.41, 2015 · Zbl 1330.05168 · doi:10.37236/5401
[53] Stanley, RP, Differential posets, J. Am. Math. Sci., 1, 4, 919-961, 1988 · Zbl 0658.05006 · doi:10.2307/1990995
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.