Hypercontractivity of spherical averages in Hamming space
Certain conditional expectation operators (stochastic matrices) have the property, called hypercontractivity (HC), that their Lp->Lq norm is 1 for p < q. HC was first discovered by Bonami and Gross for the "Bernoulli" operator acting on functions in n-dimensional Hamming space (binary hypercube). (The "Bernoulli" operator takes a real-valued function f on the Boolean cube and maps f to g given by g(x) = E_Z [(x+Z)] where Z is a Bernoulli distributed random variable.) In this talk I will prove HC of the operator where Z is uniformly distributed on a Hamming sphere (so Hamming weight of Z is constant).
There are several applications of HC in information theory (eg, Ahslwede-Gacs'76) and CS (eg, Kahn-Kalai-Linial'88). In the first part of the talk, I will talk about another application (in hypothesis testing) and about relatively modern approaches to proving HC (via the use of "log-Sobolev inequalities" and the comparison of "Dirichlet forms"). In the second part I will talk about our proof of the main result for which the previous methods fail. Instead our proof is based on harmonic analysis on the hypercube and precise asymptotics of Krawtchouk polynomials.
Time-permitting we will also show the following application of the main result: Can we approximate a uniform distribution on the Hamming sphere by a sum of two independent copies of a low-entropy r.v. X? We will give a negative answer using our HC.