Hypercontractivity on high dimensional expanders
Tom Gur, Noam Lifshitz, Siqi Liu
Abstract
We prove hypercontractive inequalities on high dimensional expanders. As in the settings of the p-biased hypercube, the symmetric group, and the Grassmann scheme, our inequalities are effective for global functions, which are functions that are not significantly affected by a restriction of a small set of coordinates. As applications, we obtain Fourier concentration, small-set expansion, and Kruskal–Katona theorems for high dimensional expanders. Our techniques rely on a new approximate Efron–Stein decomposition for high dimensional link expanders.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext 6be04204-ed92-45e3-bd0f-37f7a49aae2fCited by top-tier papers8
- Good Quantum LDPC Codes with Linear Time DecodersIrit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, Thomas VidickSTOC 2023 · 83 citations
- Constant Degree Direct Product Testers with Small SoundnessMitali Bafna, Noam Lifshitz, Dor MinzerFOCS 2024 · 4 citations
- Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXsYotam Dikstein, Irit Dinur, Alexander LubotzkyFOCS 2024 · 3 citations
- High Rate Efficient Local List Decoding from HDXYotam Dikstein, Max Hopkins, Toniann Pitassi, Russell ImpagliazzoSTOC 2026 · 3 citations
- Chernoff Bounds and Reverse Hypercontractivity on HDXYotam Dikstein, Max HopkinsFOCS 2024 · 2 citations
Builds on8
- Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore ModelNima Anari, Kuikui Liu, Shayan Oveis GharanFOCS 2020 · 97 citations
- Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansionZongchen Chen, Kuikui Liu, Eric VigodaSTOC 2021 · 61 citations
- Decodable quantum LDPC codes beyond the square root distance barrier using high dimensional expandersShai Evra, Tali Kaufman, Gilles ZémorFOCS 2020 · 33 citations
- An Invariance Principle for the Multi-slice, with ApplicationsMark Braverman, Subhash Khot, Noam Lifshitz, Dor MinzerFOCS 2021 · 29 citations
- Hypercontractivity on high dimensional expandersMitali Bafna, Max Hopkins, Tali Kaufman, Shachar LovettSTOC 2022 · 20 citations
Related papers
- Hypercontractivity on HDX II: Symmetrization and q-NormsMax HopkinsSTOC 2025
- New High Dimensional Expanders from CoversYotam DiksteinSTOC 2023 · 4 citations
- Concentration of polynomial random matrices via Efron-Stein inequalitiesGoutham Rajendran, Madhur TulsianiSODA 2023 · 5 citations
- An Analogue of Bonami's Lemma for Functions on Spaces of Linear Maps, and 2-2 GamesDavid Ellis, Guy Kindler, Noam LifshitzSTOC 2023 · 3 citations
- Spectral Hypergraph Sparsifiers of Nearly Linear SizeMichael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi YoshidaFOCS 2021 · 14 citations
