# Theory Seminar: An invariance principle for polytopes

- Speaker:
- Prahladh Harsha (TIFR, Mumbai, India)
- Date:
- Wednesday, 25.11.2009, 12:30
- Place:
- Taub 201

In this talk, I will talk about a new invariance principle for polytopes
(intersection of halfspaces) and some applications of the same.
Invariance Principle: Let X be randomly chosen from {−1,1}^n, and let Y
be randomly chosen from a spherical Gaussian on R^n. For any polytope P
formed by the intersection of k halfspaces,
|Pr[X∈P]−Pr[Y∈P]|≤polylog(k)·∆,
where ∆ is a parameter that is small for “regular” polytopes. A polytope
is said to be regular if for each of the defining halfspaces,
the influence of every variable is small. The novelty of our invariance
principle is the polylogarithmic dependence on k, as opposed to earlier
results which were at least linear in k.

Some applications of this invariance principle include

• A bound of polylog(k) · poly(ε) on the Boolean noise sensitivity of
intersections of k “regular” halfspaces. This gives a corresponding
agnostic learning algorithm for intersections of regular halfspaces
• A pseudorandom generator with seed length O(log n poly(log k, 1/δ))
that δ-fools all (not necessarily regular) polytopes with k faces with
respect to the Gaussian distribution or uniform distribution on the
sphere S^{n-1}. This for instance, gives a blackbox derandomization of
the Goemans-Williamson algorithm for MAXCUT.
• A pseudorandom generator with seed length O(log n poly(log k, 1/δ))
that δ-fools regular polytopes with k faces with respect to the uniform
distribution on the hypercube. This results yields deterministic
quasipolynomial-time algorithms for approximately counting the number of
solutions to a broad class of integer programs, including contingency
tables and dense covering problems.

[Joint work with Adam Klivans and Raghu Meka]