**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. Results **

** 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. Proof **

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

### Like this:

Like Loading...

*Related*

## 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
http://www.math.ens.fr/metric2011/