Hypercontractivity and Small-Set Expansion

Corresponds to advanced course, Lectures 21–22 (reference: O’Donnell, Analysis of Boolean Functions, Chapters 9–10). Hypercontractivity is a quantitative statement about how noise shrinks the higher Fourier levels of a Boolean function faster than the lower ones: the noise operator $T_\rho$ (replace each coordinate independently with probability related to $\rho$) is diagonal in the Fourier basis, scaling level-$k$ Fourier mass by $\rho^k$, and the Bonami lemma/the (2,4)-hypercontractive inequality make precise just how much this improves $L_p$-norm bounds — a workhorse tool throughout analysis of Boolean functions, PCP constructions, and (as here) expansion. Applying it to the “noise hypercube” (the hypercube graph where edges connect noise-correlated points rather than Hamming neighbors) proves it’s a small-set expander: unlike a generic expander, where only sets up to constant density are guaranteed to expand well, in an SSE even very small sets (density going to 0) still expand almost perfectly — a stronger property with its own applications in hardness-of-approximation and the Unique Games Conjecture literature.

Outline (TODO — flesh out each)

• $L_p$ norms and their inequalities
• The noise operator and its diagonal (Fourier) form
• The Bonami lemma
• The (2,4)-hypercontractive inequality
• The noise hypercube
• Small-set expanders (SSE) and their properties