Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR21-168 | 24th December 2021 04:28

Hypercontractivity on High Dimensional Expanders: Approximate Efron-Stein Decompositions for $\epsilon$-Product Spaces

RSS-Feed




Revision #2
Authors: Tom Gur, Noam Lifshitz, Siqi Liu
Accepted on: 24th December 2021 04:28
Downloads: 272
Keywords: 


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.


Revision #1 to TR21-168 | 24th November 2021 21:18

Hypercontractivity on High Dimensional Expanders: Approximate Efron-Stein Decompositions for $\epsilon$-Product Spaces





Revision #1
Authors: Tom Gur, Noam Lifshitz, Siqi Liu
Accepted on: 24th November 2021 21:18
Downloads: 261
Keywords: 


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.



Changes to previous version:

Added a secondary title to distinguish between ECCC TR21-169


Paper:

TR21-168 | 17th November 2021 21:54

Hypercontractivity on High Dimensional Expanders: Approximate Efron-Stein Decompositions for $\epsilon$-Product Spaces





TR21-168
Authors: Tom Gur, Noam Lifshitz, Siqi Liu
Publication: 24th November 2021 10:10
Downloads: 456
Keywords: 


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.



ISSN 1433-8092 | Imprint