The Taub Faculty of Computer Science Events and Talks

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]