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 are iid random variables, then converges to a Gaussian in distance.
1.2. Berry-Esséen Theorem
Let be the sign of a linear form. Let be iid Boolean variables. Let be iid Gaussian variables. Then and are close in distance.
1.3. Mossel, O’Donnell, Oleskiewicz’ Invariance principle
Let be uniformly distributed and be a Gaussian vector. Let be a Boolean function with low influences and no high frequencies. Then
Used in the proof of Majority is stablest theorem, and in Meka-Zuckerman’s construction of pseudorandom generators.
2.1. Main result
Let be defined by unit norm hyperplanes (tangent to the unit sphere), which are -regular (i.e. none of them has large influence). Let be uniformly distributed and be a Gaussian vector. Then
2.2. Application to noise sensitivity of polytopes
Also applies to learning polytopes.
2.3. Application to pseudorandom generators for polytopes
There exists a PRG of seed length
that -fools 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.1. Why do we believe in it
Nazarov’s theorem (Gaussian volume of tubular neighborhood of boundary of a -face polytope is is an indication that our theorem might be true.
3.2. The proof
We follow the [MOO]’s strategy: Approximate characteristic function of with a 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 with norm of polylog size.
- Nazarov’s bound on Gaussian surface area.
3.3. Open problems
Handle all polytopes and no merely regular ones.