Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2209.04243 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912838751092736 |
|---|---|
| author | Ellis, David Kindler, Guy Lifshitz, Noam |
| author_facet | Ellis, David Kindler, Guy Lifshitz, Noam |
| contents | We prove an analogue of Bonami's (hypercontractive) lemma for complex-valued functions on $\mathcal{L}(V,W)$, where $V$ and $W$ are vector spaces over a finite field. This inequality is useful for functions on $\mathcal{L}(V,W)$ whose `generalised influences' are small, in an appropriate sense. It leads to a significant shortening of the proof of a recent seminal result by Khot, Minzer and Safra that pseudorandom sets in Grassmann graphs have near-perfect expansion, which (in combination with the work of Dinur, Khot, Kindler, Minzer and Safra) implies the 2-2 Games conjecture (the variant, that is, with imperfect completeness). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_04243 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | An analogue of Bonami's Lemma for functions on spaces of linear maps, and 2-2 Games Ellis, David Kindler, Guy Lifshitz, Noam Combinatorics Functional Analysis Probability 06E30 F.2.2 We prove an analogue of Bonami's (hypercontractive) lemma for complex-valued functions on $\mathcal{L}(V,W)$, where $V$ and $W$ are vector spaces over a finite field. This inequality is useful for functions on $\mathcal{L}(V,W)$ whose `generalised influences' are small, in an appropriate sense. It leads to a significant shortening of the proof of a recent seminal result by Khot, Minzer and Safra that pseudorandom sets in Grassmann graphs have near-perfect expansion, which (in combination with the work of Dinur, Khot, Kindler, Minzer and Safra) implies the 2-2 Games conjecture (the variant, that is, with imperfect completeness). |
| title | An analogue of Bonami's Lemma for functions on spaces of linear maps, and 2-2 Games |
| topic | Combinatorics Functional Analysis Probability 06E30 F.2.2 |
| url | https://arxiv.org/abs/2209.04243 |