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.

 

Advertisements

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/
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:

WordPress.com Logo

You are commenting using your WordPress.com 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