An Analogue of Bonami's Lemma for Functions on Spaces of Linear Maps, and 2-2 Games

We prove an analogue of Bonami’s (hypercontractive) lemma for complex-valued functions on L (𝑉,𝑊 ), where 𝑉 and 𝑊 are vector spaces over a finite field. This inequality is useful for functions on L (𝑉,𝑊 ) 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)

Authors

• David Ellis
• Guy Kindler
• Noam Lifshitz

Keywords

• Boolean functions
• Fourier
• Games
• Hypercontractivity