My student Punya Biswal just completed this great survey on hypercontractivity and its application in computer science. There is a PDF version from his home page, and accompanying slides.

Hypercontractive inequalities are a useful tool in dealing with extremal questions in the geometry of high-dimensional discrete and continuous spaces. In this survey we trace a few connections between different manifestations of hypercontractivity, and also present some relatively recent applications of these techniques in computer science.

### 1. Preliminaries and notation

**Fourier analysis on the hypercube.** We define the inner product on functions , where the expectation is taken over the uniform (counting) measure on . The multilinear polynomials (where ranges over subsets of ) form an orthogonal basis under this inner product; they are called the Fourier basis. Thus, for any function , we have , where the Fourier coefficients obey Plancherel’s relation . It is easy to verify that and .

**Norms.** For , define the norm . These norms are monotone in : for every function , implies . For a linear operator carrying functions to functions , we define the -to- operator norm . is said to be a contraction from to when . Because of the monotonicity of norms, a contraction from to is automatically a contraction from to for any . When and , then is said to be hypercontractive.

**Convolution operators.** Letting represent the coordinatewise product of , we define the convolution of two functions , and note that it is a linear operator for every fixed . Convolution is commutative and associative, and the Fourier coefficients of a convolution satisfy the useful property . We shall be particularly interested in the convolution properties of the following functions

- The Dirac delta , given by and otherwise. It is the identity for convolution and has for all .
- The edge functions given by
is or according as contains or does not contain , respectively. For any function , , where is obtained from by flipping just the th bit. Convolution with acts as an orthogonal projection (as we can easily see in the Fourier domain), so for any functions , we have

- The Bonami-Gross-Beckner noise functions for , where and we define . These operators form a semigroup, because and . Note that . We define the noise operator acting on functions on the discrete cube by . In combinatorial terms, is the expected value of , where is obtained from by independently flipping each bit of with probability .

**Lemma 1** * *

*Proof:* This is easy in the Fourier basis:

Continue reading →