## 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.