Log Concavity and Concentration of Measure on the Discrete Hypercube

Log Concavity and Concentration of Measure on the Discrete Hypercube

-
Ronen Eldan (Weizmann and IAS)
Fine Hall 401

It is well known that if $V: \mathbb{R}^n \to \mathbb{R}$ is a uniformly convex potential then the measure whose density with respect to the Lebesgue measure on $\mathbb{R}^n$ is $e^{-V}$, satisfies several concentration properties (such as a Poincaré inequality and the fact that Lipschitz functions have a sub-Gaussian tail). In this talk, we try to find analogs of this fact when $\mathbb{R}^n$ is replaced by the Boolean hypercube, hence, the density $e^{-V}$ is with respect to the uniform measure on the Boolean hypercube. In this case, it is not clear what should be the correct definition of log-concavity, and even when $V$ is quadratic (which is trivial in the Gaussian case), proving concentration becomes a challenging question (with implications to spin-glasses, for example). We'll present two results in this direction: First, we will suggest a natural definition of log-concavity which attains such concentration, namely, in terms of the (semi) log-concavity of the multilinear extension. Second, we will present a result which gives sufficient conditions for concentration of quadratic forms, and in particular implies that the Gibbs measure on the Sherrington-Kirkpatrick model admits concentration when the temperature is higher than some universal constant. Based on joint works with Koehler, Shamir and Zeitouni.