Notes of Adam Klivans’ talk


An invariance principle for polytopes


1. Invariance principles


Instead of giving a formal definition, I will give examples of invariance principle.


1.1. Central Limit Theorem


If {X_i} are iid random variables, then {\sum_i X_i} converges to a Gaussian in {CDF} distance.


1.2. Berry-Esséen Theorem


Let {f} be the sign of a linear form. Let {x_i} be iid Boolean variables. Let {Y_i} be iid Gaussian variables. Then {f(x_1 ,\ldots,x_n)} and {f(Y_1 ,\ldots,Y_n)} are close in {CDF} distance.


1.3. Mossel, O’Donnell, Oleskiewicz’ Invariance principle


Let {x\in\{\pm 1\}^n} be uniformly distributed and {Y} be a Gaussian vector. Let {f} be a Boolean function with low influences and no high frequencies. Then

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb E}_x (f(x))-\mathop{\mathbb E}_Y (f(Y))| \textrm{ is small}. \end{array}

Used in the proof of Majority is stablest theorem, and in Meka-Zuckerman’s construction of pseudorandom generators.


2. Results


2.1. Main result


Let {K} be defined by {k} unit norm hyperplanes (tangent to the unit sphere), which are {\epsilon}-regular (i.e. none of them has large influence). Let {x\in\{\pm 1\}^n} be uniformly distributed and {Y} be a Gaussian vector. Then

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb P}_x (x\in K)-\mathop{\mathbb P}_Y (Y\in K)|\leq \mathrm{polylog}(k)\,\mathrm{poly}(\epsilon). \end{array}


2.2. Application to noise sensitivity of polytopes


\displaystyle  \begin{array}{rcl}  NS_{\epsilon}(f)\leq (\log k)^{O(1)}\epsilon^{1/6}. \end{array}

Also applies to learning polytopes.


2.3. Application to pseudorandom generators for polytopes


There exists a PRG of seed length

\displaystyle  \begin{array}{rcl}  r=\log n \,\mathrm{polylog}(k)\,\mathrm{poly}(\frac{1}{\Delta}), \end{array}

that {\Delta}-fools {k} face polytopes.


2.4. Application to deterministic counting solutions to integer programs


I.e. counting integer points in a polytope. Restricted to regular polytopes. But Ailon and Chazelle show that a random rotation makes an arbitrary polytope regular. Meka and Zuckerman reduced the amount of randomness, and we further improve on it.


3. Proof


3.1. Why do we believe in it


Nazarov’s theorem (Gaussian volume of tubular neighborhood of boundary of a {k}-face polytope is {O(\sqrt{\log k})} is an indication that our theorem might be true.


3.2. The proof


We follow the [MOO]’s strategy: Approximate characteristic function of {K} with a {C^4} function, replace Boolean by Gaussian variables one by one. Use Taylor expansion and hypercontractivity. But use extra tricks:

  • Randomly group coordinates in blocks (idea from Rabani-Shpilka). This is a way of replacing maximal influence by certain averages of influences.
  • A paper by V. Bentkus provides a smooth Gaussian-like approximation of characteristic function of {K} with {C^4} norm of polylog{(k)} size.
  • Nazarov’s bound on Gaussian surface area.


3.3. Open problems


Handle all polytopes and no merely regular ones.



About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s