Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

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: 22
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: 46
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