REVIEW 2 minor 82 references
Toward a KKL Theorem for any HDX
T0 review · 0 major / 2 minor · reviewed 2026-06-30 · grok-4.3
Pith's one-line read Any simplicial complex inherits a KKL theorem from its links via a local-to-global argument.
desk verdict The paper gives a local-to-global lift for KKL results on simplicial complexes, relaxing the strong expansion needed in the 2022 STOC papers and reaching clique complexes plus Ramanujan complexes. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
A simple local-to-global method for analyzing low-influence functions on simplicial complexes.
What would settle it
A simplicial complex in which every link satisfies a KKL theorem but the global complex fails to exhibit the corresponding low-influence structure would disprove the local-to-global transfer.
Extended reading notes
Core claim
The central discovery is a local-to-global KKL theorem: any simplicial complex whose links satisfy a KKL theorem also satisfies one globally. Building on prior work, a dimension-dependent version holds for any non-trivially expanding complex. This yields the first characterization of non-expanding functions on dense clique complexes together with a Kruskal-Katona theorem and a small-set expansion result for Ramanujan complexes.
Load-bearing premise
The links of the simplicial complex must themselves satisfy a KKL theorem, or the complex must have non-trivial two-sided expansion.
Editorial extensions
If this is right
- First characterization of non-expanding functions on dense clique complexes.
- Corresponding Kruskal-Katona theorem for those complexes.
- Small-set expansion theorem for Ramanujan complexes.
- KKL-type results now hold without the strong quantitative expansion requirements of earlier HDX theorems.
Reading between the lines
- The method suggests that verifying KKL on small links may suffice for global results across many complexes.
- It could extend to other local-to-global phenomena in high-dimensional expanders beyond KKL.
- Similar transfers might apply to additional theorems from boolean analysis on HDX.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript introduces a local-to-global method for low-influence functions on simplicial complexes. It proves that any simplicial complex whose links satisfy a KKL theorem also satisfies a global KKL-type result, and establishes a weaker dimension-dependent version for complexes with non-trivial two-sided expansion (building on Gotlib-Kaufman). Applications include the first characterization of non-expanding functions on combinatorial HDX such as dense clique complexes (with a corresponding Kruskal-Katona theorem) and a small-set expansion result for the Ramanujan complexes of Lubotzky-Samuels-Vishne.
Significance. If the transfer argument holds, the work removes the strong quantitative expansion barriers of prior KKL analogs on HDX (Bafna et al., Gur et al.) and supplies a general framework applicable whenever links satisfy the local property. The weaker result for arbitrary non-trivial expansion and the concrete applications to combinatorial HDX and Ramanujan complexes are concrete strengths; the conditional structure of the main theorem is stated clearly.
minor comments (2)
- [Abstract] Abstract: the phrase 'combinatorial HDX such as dense clique complexes' is used without a precise definition or citation to the exact class of complexes; adding a one-sentence clarification would improve readability.
- [Introduction] The dimension dependence of the weaker theorem is noted in the abstract but should be stated quantitatively (e.g., the precise dependence on dimension d) in the introduction or theorem statement for immediate comparison with prior work.
Simulated Author's Rebuttal
We thank the referee for their positive summary of the manuscript and for recommending minor revision. The report correctly identifies the local-to-global transfer as the central contribution and notes the concrete applications to combinatorial HDX and Ramanujan complexes.
Circularity Check
No significant circularity identified
full rationale
The paper establishes a conditional local-to-global transfer theorem: if the links of a simplicial complex satisfy a KKL-type result, then the complex does globally (or a weaker dimension-dependent version under non-trivial two-sided expansion). This is presented as the output of a new analysis method, with the hypothesis stated explicitly as an assumption rather than derived internally. No equation or step reduces a claimed prediction or first-principles result to a fitted parameter, self-definition, or unverified self-citation chain; prior citations (including self-citations to Bafna-Hopkins et al.) supply independent support for the local case without the global claim collapsing to them by construction. The derivation chain is therefore self-contained against external benchmarks.
Assumptions & free parameters
assumptions (2)
- domain assumption Links of a simplicial complex are themselves simplicial complexes of lower dimension.
- domain assumption Non-trivial two-sided expansion is a well-defined property of simplicial complexes.
Cite this review
Pith. "Pith review of Toward a KKL Theorem for any HDX." pith.science (2026). https://pith.science/paper/RFWYWJJO
@misc{pith2026260629449,
author = {Pith},
title = {Pith review of: Toward a KKL Theorem for any HDX},
year = {2026},
howpublished = {\url{https://pith.science/paper/RFWYWJJO}},
note = {Machine review of arXiv:2606.29449}
}
read the original abstract
The KKL Theorem, a seminal result in boolean function analysis, characterizes the structure of low-influence (non-expanding) functions on the hypercube. While recent years have seen breakthrough results across a variety of areas relying on analogs of the KKL Theorem beyond the cube (e.g., on product spaces, Grassmann graphs), further progress has been inhibited by our poor understanding of the phenomenon across more general domains. Motivated in this context, Bafna, Hopkins, Kaufman, and Lovett (STOC 2022) and Gur, Lifshitz, and Liu (STOC 2022) proved a generalized KKL-type Theorem for spectral high dimensional expanders (HDX). Their results, however, remain highly restricted due to strong quantitative expansion requirements on the underlying complex. In this work, we introduce a simple local-to-global method for analyzing low influence functions on simplicial complexes. Using this method we prove a local-to-global KKL-type Theorem: any simplicial complex whose links satisfy a KKL-Theorem also satisfies such a result globally. Building on Gotlib and Kaufman (RANDOM 2023), we also prove a weaker dimension-dependent KKL-type Theorem for simplicial complexes with any non-trivial (two-sided) expansion. As concrete applications of our framework, we give the first characterization of non-expanding functions on `combinatorial' HDX such as dense clique complexes and a corresponding Kruskal-Katona Theorem, as well as a small-set expansion theorem for the Ramanujan Complexes of Lubotzky, Samuels, and Vishne (EJC '05).
Reference graph
Works this paper leans on
-
[1]
J. Kahn, G. Kalai, and N. Linial. The influence of variables on boolean functions. In2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 68–80, Los Alamitos, CA, USA, oct
-
[2]
IEEE Computer Society
-
[3]
The influence of variables in product spaces.Israel Journal of Mathematics, 77(1):55–64, 1992
Jean Bourgain, Jeff Kahn, Gil Kalai, Yitzhak Katznelson, and Nathan Linial. The influence of variables in product spaces.Israel Journal of Mathematics, 77(1):55–64, 1992. 25
1992
-
[4]
On Russo’s approximate zero-one law.The Annals of Probability, pages 1576–1587, 1994
Michel Talagrand. On Russo’s approximate zero-one law.The Annals of Probability, pages 1576–1587, 1994
1994
-
[5]
Every monotone graph property has a sharp threshold.Proceedings of the American mathematical Society, 124(10):2993–3002, 1996
Ehud Friedgut and Gil Kalai. Every monotone graph property has a sharp threshold.Proceedings of the American mathematical Society, 124(10):2993–3002, 1996
1996
-
[6]
Boolean functions with low average sensitivity depend on few coordinates.Combinatorica, 18(1):27–35, 1998
Ehud Friedgut. Boolean functions with low average sensitivity depend on few coordinates.Combinatorica, 18(1):27–35, 1998
1998
-
[7]
A structure theorem for boolean functions with small total influences.Annals of Mathematics, pages 509–533, 2012
Hamed Hatami. A structure theorem for boolean functions with small total influences.Annals of Mathematics, pages 509–533, 2012
2012
-
[8]
Hypercontractivity for global functions and sharp thresholds
Peter Keevash, Noam Lifshitz, Eoin Long, and Dor Minzer. Hypercontractivity for global functions and sharp thresholds. Journal of the American Mathematical Society, 37(1):245–279, 2024
2024
Show all 82 references
-
[9]
Noise sensitivity on the p-biased hypercube
Noam Lifshitz and Dor Minzer. Noise sensitivity on the p-biased hypercube. In2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1205–1226. IEEE, 2019
2019
-
[10]
Product mixing in compact lie groups
David Ellis, Guy Kindler, Noam Lifshitz, and Dor Minzer. Product mixing in compact lie groups. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1415–1422, 2024
2024
-
[11]
Pseudorandom sets in grassmann graph have near-perfect expansion
Subhash Khot, Dor Minzer, and Muli Safra. Pseudorandom sets in grassmann graph have near-perfect expansion. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 592–601. IEEE, 2018
2018
-
[12]
An analogue of bonami’s lemma for functions on spaces of linear maps, and 2-2 games
David Ellis, Guy Kindler, and Noam Lifshitz. An analogue of bonami’s lemma for functions on spaces of linear maps, and 2-2 games. InProceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 656–660, 2023
2023
-
[13]
Sharp thresholds of graph properties, and the k-sat problem.Journal of the American mathematical Society, 12(4):1017–1054, 1999
Ehud Friedgut and Jean Bourgain. Sharp thresholds of graph properties, and the k-sat problem.Journal of the American mathematical Society, 12(4):1017–1054, 1999
1999
-
[14]
On independent sets, 2-to-2 games, and grassmann graphs
Subhash Khot, Dor Minzer, and Muli Safra. On independent sets, 2-to-2 games, and grassmann graphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 576–589, 2017
2017
-
[15]
Towards a proof of the 2-to-1 games conjecture? In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 376–389, 2018
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. Towards a proof of the 2-to-1 games conjecture? In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 376–389, 2018
2018
-
[16]
On non-optimally expanding sets in grassmann graphs
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. On non-optimally expanding sets in grassmann graphs. InProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 940–951, 2018
2018
-
[17]
Small-set expansion in shortcode graph and the 2-to-2 conjecture
Boaz Barak, Pravesh K Kothari, and David Steurer. Small-set expansion in shortcode graph and the 2-to-2 conjecture. In10th Innovations in Theoretical Computer Science Conference (ITCS 2019), pages 9–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2019
2019
-
[18]
Small-set expansion in the johnson graph
Subhash Khot, Dor Minzer, Dana Moshkovitz, and Muli Safra. Small-set expansion in the johnson graph. Theory of Computing, 21(1):1–43, 2025
2025
-
[19]
Near optimal alphabet-soundness tradeoff pcps
Dor Minzer and Kai Zhe Zheng. Near optimal alphabet-soundness tradeoff pcps. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 15–23, 2024
2024
-
[20]
Multi-pass streaming lower bounds for approximating max-cut
Yumou Fei, Dor Minzer, and Shuo Wang. Multi-pass streaming lower bounds for approximating max-cut. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 1537–1560, 2025
2025
-
[21]
Sharp hypercontractivity for global functions.Journal of the European Mathematical Society, 2026
Nathan Keller, Noam Lifshitz, and Omri Marcus. Sharp hypercontractivity for global functions.Journal of the European Mathematical Society, 2026. Published online first. 26
2026
-
[22]
On the largest product-free subsets of the alternating groups
Peter Keevash, Noam Lifshitz, and Dor Minzer. On the largest product-free subsets of the alternating groups. Inventiones mathematicae, 237(3):1329–1375, 2024
2024
-
[23]
On t-intersecting families of permutations
Nathan Keller, Noam Lifshitz, Dor Minzer, and Ohad Sheinfeld. On t-intersecting families of permutations. Advances in Mathematics, 445:109650, 2024
2024
-
[24]
New bounds for the furstenberg-s\’ark\" ozy theorem.arXiv preprint arXiv:2411.17448, 2024
Ben Green and Mehtaab Sawhney. New bounds for the furstenberg-s\’ark\" ozy theorem.arXiv preprint arXiv:2411.17448, 2024
2024
-
[25]
High order random walks: Beyond spectral gap.Combinatorica, pages 1–37, 2020
Tali Kaufman and Izhar Oppenheim. High order random walks: Beyond spectral gap.Combinatorica, pages 1–37, 2020
2020
-
[26]
Boolean function analysis on high- dimensional expanders
Yotam Dikstein, Irit Dinur, Yuval Filmus, and Prahladh Harsha. Boolean function analysis on high- dimensional expanders. InApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Inform...
2018
-
[27]
High dimensional expanders: Eigenstrip- ping, pseudorandomness, and unique games
Mitali Bafna, Max Hopkins, Tali Kaufman, and Shachar Lovett. High dimensional expanders: Eigenstrip- ping, pseudorandomness, and unique games. InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1069–1128. SIAM, 2022
2022
-
[28]
Hypercontractivity on high dimensional expanders
Mitali Bafna, Max Hopkins, Tali Kaufman, and Shachar Lovett. Hypercontractivity on high dimensional expanders. InProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 185–194, 2022
2022
-
[29]
Hypercontractivity on high dimensional expanders
Tom Gur, Noam Lifshitz, and Siqi Liu. Hypercontractivity on high dimensional expanders. InProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 176–184, 2022
2022
-
[30]
Eigenstripping, spectral decay, and edge-expansion on posets
Jason Gaitonde, Max Hopkins, Tali Kaufman, Shachar Lovett, and Ruizhe Zhang. Eigenstripping, spectral decay, and edge-expansion on posets. InApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022), pages 16–1. Schloss Dagstu...
2022
-
[31]
Hypercontractivity on hdx ii: Symmetrization andq-norms
Max Hopkins. Hypercontractivity on hdx ii: Symmetrization andq-norms. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 96–103, 2025
2025
-
[32]
High dimensional expanders imply agreement expanders
Irit Dinur and Tali Kaufman. High dimensional expanders imply agreement expanders. In2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 974–985. IEEE, 2017
2017
-
[33]
Agreement testing theorems on layered set systems
Yotam Dikstein and Irit Dinur. Agreement testing theorems on layered set systems. In2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1495–1524. IEEE, 2019
2019
-
[34]
Local-to-global agreement expansion via the variance method
Tali Kaufman and David Mass. Local-to-global agreement expansion via the variance method. In11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020
2020
-
[35]
Approximating constraint satisfaction problems on high-dimensional expanders
Vedat Levi Alev, Fernando Granha Jeronimo, and Madhur Tulsiani. Approximating constraint satisfaction problems on high-dimensional expanders. In2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 180–201. IEEE, 2019
2019
-
[36]
Explicit sos lower bounds from high-dimensional expanders
Irit Dinur, Yuval Filmus, Prahladh Harsha, and Madhur Tulsiani. Explicit sos lower bounds from high-dimensional expanders. In12th Innovations in Theoretical Computer Science Conference, ITCS 2021, pages 1–16. Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publi...
2021
-
[37]
Explicit lower bounds againstω (n)-rounds of sum-of-squares
Max Hopkins and Ting-Chun Lin. Explicit lower bounds againstω (n)-rounds of sum-of-squares. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 662–673. IEEE, 2022
2022
-
[38]
Sampling equilibria: Fast no-regret learning in structured games
Daniel Beaglehole, Max Hopkins, Daniel Kane, Sihan Liu, and Shachar Lovett. Sampling equilibria: Fast no-regret learning in structured games. InProceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3817–3855. SIAM, 2023. 27
2023
-
[39]
Log-concave polynomials ii: high-dimensional walks and an FPRAS for counting bases of a matroid
Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant. Log-concave polynomials ii: high-dimensional walks and an FPRAS for counting bases of a matroid. InProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 1–12, 2019
2019
-
[40]
Improved analysis of higher order random walks and applications
Vedat Levi Alev and Lap Chi Lau. Improved analysis of higher order random walks and applications. In Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, pages 1198–1211, 2020
2020
-
[41]
Spectral independence in high-dimensional expanders and applications to the hardcore model.SIAM Journal on Computing, 53(6):FOCS20–1, 2021
Nima Anari, Kuikui Liu, and Shayan Oveis Gharan. Spectral independence in high-dimensional expanders and applications to the hardcore model.SIAM Journal on Computing, 53(6):FOCS20–1, 2021
2021
-
[42]
Rapid mixing of glauber dynamics up to uniqueness via contraction
Zongchen Chen, Kuikui Liu, and Eric Vigoda. Rapid mixing of glauber dynamics up to uniqueness via contraction. SIAM Journal on Computing, 52(1):196–237, 2023
2023
-
[43]
Optimal mixing of glauber dynamics: Entropy factorization via high-dimensional expansion
Zongchen Chen, Kuikui Liu, and Eric Vigoda. Optimal mixing of glauber dynamics: Entropy factorization via high-dimensional expansion. InProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1537–1550, 2021
2021
-
[44]
Rapid mixing for colorings via spectral independence
Zongchen Chen, Andreas Galanis, Daniel Štefankovič, and Eric Vigoda. Rapid mixing for colorings via spectral independence. InProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1548–1557. SIAM, 2021
2021
-
[45]
Rapid mixing from spectral independence beyond the boolean domain
Weiming Feng, Heng Guo, Yitong Yin, and Chihao Zhang. Rapid mixing from spectral independence beyond the boolean domain. InProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1558–1577. SIAM, 2021
2021
-
[46]
Spectral independence, coupling, and the spectral gap of the glauber dynamics.Information Processing Letters, 177:106268, 2022
Vishesh Jain, Huy Tuan Pham, and Thuy-Duong Vuong. Spectral independence, coupling, and the spectral gap of the glauber dynamics.Information Processing Letters, 177:106268, 2022
2022
-
[47]
From coupling to spectral independence and blackbox comparison with the down-up walk
Kuikui Liu. From coupling to spectral independence and blackbox comparison with the down-up walk. InApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), pages 32–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2021
2021
-
[48]
On mixing of markov chains: Coupling, spectral independence, and entropy factorization
Antonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Parisi, Daniel Štefankovič, and Eric Vigoda. On mixing of markov chains: Coupling, spectral independence, and entropy factorization. InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 36...
2022
-
[49]
Locally testable codes with constant rate, distance, and locality
Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes. Locally testable codes with constant rate, distance, and locality. InProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 357–374, 2022
2022
-
[50]
Asymptotically good quantum and locally testable classical ldpc codes
Pavel Panteleev and Gleb Kalachev. Asymptotically good quantum and locally testable classical ldpc codes. In Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, pages 375–388, 2022
2022
-
[51]
New codes on high dimensional expanders
Irit Dinur, Siqi Liu, and Rachel Yun Zhang. New codes on high dimensional expanders. In40th Computational Complexity Conference, CCC 2025, page 27. Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2025
2025
-
[52]
Chernoff bounds and reverse hypercontractivity on hdx
Yotam Dikstein and Max Hopkins. Chernoff bounds and reverse hypercontractivity on hdx. In2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 870–919. IEEE, 2024
2024
-
[53]
Low acceptance agreement tests via bounded-degree symplectic hdxs
Yotam Dikstein, Irit Dinur, and Alexander Lubotzky. Low acceptance agreement tests via bounded-degree symplectic hdxs. In2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 826–861. IEEE, 2024. 28
2024
-
[54]
Constant degree direct product testers with small soundness
Mitali Bafna, Noam Lifshitz, and Dor Minzer. Constant degree direct product testers with small soundness. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 862–869. IEEE, 2024
2024
-
[55]
Quasi-linear size pcps with small soundness from hdx
Mitali Bafna, Dor Minzer, Nikhil Vyas, and Zhiwei Yun. Quasi-linear size pcps with small soundness from hdx. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 45–53, 2025
2025
-
[56]
Explicit lossless vertex expanders
Jun-Ting Hsieh, Alexander Lubotzky, Sidhanth Mohanty, Assaf Reiner, and Rachel Yun Zhang. Explicit lossless vertex expanders. In2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 894–911, 2025
2025
-
[57]
3-query rldcs are strictly stronger than 3-query ldcs
Tom Gur, Dor Minzer, Guy Weissenberg, and Kai Zhe Zheng. 3-query rldcs are strictly stronger than 3-query ldcs. arXiv preprint arXiv:2512.12960, 2025
2025
-
[58]
High rate efficient local list decoding from hdx.arXiv preprint arXiv:2601.22535, 2026
Yotam Dikstein, Max Hopkins, Russell Impagliazzo, and Toniann Pitassi. High rate efficient local list decoding from hdx.arXiv preprint arXiv:2601.22535, 2026
2026
-
[59]
Explicit constructions of ramanujan complexes of type Ad
Alexander Lubotzky, Beth Samuels, and Uzi Vishne. Explicit constructions of ramanujan complexes of type Ad. European Journal of Combinatorics, 26(6):965–993, 2005
2005
-
[60]
Construction of new local spectral high dimensional expanders
Tali Kaufman and Izhar Oppenheim. Construction of new local spectral high dimensional expanders. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 773–786, 2018
2018
-
[61]
New high dimensional expanders from covers
Yotam Dikstein. New high dimensional expanders from covers. InProceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 826–838, 2023
2023
-
[62]
Improved product-based high-dimensional expanders
Louis Golowich. Improved product-based high-dimensional expanders. InApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), pages 38–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2021
2021
-
[63]
Fine grained analysis of high dimensional random walks.Approximation, Randomization, and Combinatorial Optimization
Roy Gotlib and Tali Kaufman. Fine grained analysis of high dimensional random walks.Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2023
2023
-
[64]
Isoperimetric inequalities for ramanujan complexes and topological expanders.Geometric and Functional Analysis, 26(1):250–287, 2016
Tali Kaufman, David Kazhdan, and Alexander Lubotzky. Isoperimetric inequalities for ramanujan complexes and topological expanders.Geometric and Functional Analysis, 26(1):250–287, 2016
2016
-
[65]
Local spectral expansion approach to high dimensional expanders part i: Descent of spectral gaps
Izhar Oppenheim. Local spectral expansion approach to high dimensional expanders part i: Descent of spectral gaps. Discrete & Computational Geometry, 59(2):293–330, 2018
2018
-
[66]
Spreading of sets in product spaces and hypercontraction of the markov operator.The annals of probability, pages 925–939, 1976
Rudolf Ahlswede and Peter Gács. Spreading of sets in product spaces and hypercontraction of the markov operator.The annals of probability, pages 925–939, 1976
1976
-
[67]
Log-sobolev inequality for the multislice, with applications
Yuval Filmus, Ryan O’Donnell, and Xinyu Wu. Log-sobolev inequality for the multislice, with applications. Electronic Journal of Probability, 27:1–30, 2022
2022
-
[68]
A sharp log-sobolev inequality for the multislice.Annales Henri Lebesgue, 4:1143–1161, 2021
Justin Salez. A sharp log-sobolev inequality for the multislice.Annales Henri Lebesgue, 4:1143–1161, 2021
2021
-
[69]
Hypercontractivity on the symmetric group
Yuval Filmus, Guy Kindler, Noam Lifshitz, and Dor Minzer. Hypercontractivity on the symmetric group. In Forum of Mathematics, Sigma, volume 12, page e6. Cambridge University Press, 2024
2024
-
[70]
Forbidden intersection problems for families of linear maps
David C Ellis, Guy Kindler, and Noam Lifshitz. Forbidden intersection problems for families of linear maps. Discrete Analysis, 19, 2023
2023
-
[71]
Beyond the worst case: Structured convergence of high dimensional random walks.CoRR, 2022
Roy Gotlib and Tali Kaufman. Beyond the worst case: Structured convergence of high dimensional random walks.CoRR, 2022. 29
2022
-
[72]
High dimensional random walks and colorful expansion
Tali Kaufman and David Mass. High dimensional random walks and colorful expansion. In8th Innovations in Theoretical Computer Science Conference (ITCS 2017), pages 4–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2017
2017
-
[73]
p-adic curvature and the cohomology of discrete subgroups of p-adic groups.Annals of Mathematics, pages 375–423, 1973
Howard Garland. p-adic curvature and the cohomology of discrete subgroups of p-adic groups.Annals of Mathematics, pages 375–423, 1973
1973
-
[74]
High dimensional expanders and property testing
Tali Kaufman and Alexander Lubotzky. High dimensional expanders and property testing. InProceedings of the 5th conference on Innovations in theoretical computer science, pages 501–506, 2014
2014
-
[75]
Decodable quantum LDPC codes beyond the square root distance barrier using high dimensional expanders
Shai Evra, Tali Kaufman, and Gilles Zémor. Decodable quantum LDPC codes beyond the square root distance barrier using high dimensional expanders. In61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 218–227, 2020
2020
-
[76]
Tali Kaufman and Ran J. Tessler. New cosystolic expanders from tensors imply explicit quantum LDPC codes with Ω(√n logk n) distance. InSTOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1317–1329, 2021. A Fourier An...
2021
-
[77]
If (X, Π) is a γ-one-sided HDX, then it is a γ 1−(d−2)γ-product
-
[78]
The first result is [32, Corollary 7.6], and follows from a partite variant of the Trickling-Down Theorem
If (X, Π) is a γ-product, it is a γ 1−(d−2)γ-one-sided HDX Proof. The first result is [32, Corollary 7.6], and follows from a partite variant of the Trickling-Down Theorem. To prove the second, observe that
-
[79]
For τ ∈ X(d − 2): Aτ = M1,2 τ ,
-
[80]
GLL show thatγ-products, and therefore partite one-sided HDX, have an approximate Fourier basis
For anyi ≤ d − 2 and τ ∈ X(i): Aτ is connected.12 Since we are promisedλ2(M1,2 τ ) ≤ γ < 1 d−1 and all links are connected, Trickling-Down (Theorem 2.16) implies the result. GLL show thatγ-products, and therefore partite one-sided HDX, have an approximate Fourier basis. Their ...
-
[81]
By construction, vi and vj are then also disconnected in M i,j τ , which violates the expansion assumption
if S ⊆ T : ET f=S = f=S 12if Aτ is disconnected, there exist disconnected verticesvi and vj of colors i and j. By construction, vi and vj are then also disconnected in M i,j τ , which violates the expansion assumption. 31
-
[82]
With this in mind, the proof of Theorem 4.3 follows easily from expandingf into the Efron-Stein basis
If S ⊈ T : ∥ET f=S∥2 ≤ p |S||T |2|S|γ∥f ∥ high order random walks on partite complexes can typically be written as convex combinations of the partite averaging operators. With this in mind, the proof of Theorem 4.3 follows easily from expandingf into the Efron-Stein basis. Pro...
Reviewed June 30, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.