An Invariance Principle for Polytopes
  Let X be randomly chosen from {-1,1}^n, and let Y be randomly chosen from the
standard spherical Gaussian on R^n. For any (possibly unbounded) polytope P
formed by the intersection of k halfspaces, we prove that
  |Pr [X belongs to P] - Pr [Y belongs to P]| < log^{8/5}k * Delta, where Delta
is a parameter that is small for polytopes formed by the intersection of
"regular" halfspaces (i.e., halfspaces with low influence). The novelty of our
invariance principle is the polylogarithmic dependence on k. Previously, only
bounds that were at least linear in k were known. We give two important
applications of our main result: (1) A polylogarithmic in k bound on the
Boolean noise sensitivity of intersections of k "regular" halfspaces (previous
work gave bounds linear in k). (2) A pseudorandom generator (PRG) with seed
length O((log n)*poly(log k,1/delta)) that delta-fools all polytopes with k
faces with respect to the Gaussian distribution. We also obtain PRGs with
similar parameters that fool polytopes formed by intersection of regular
halfspaces over the hypercube. Using our PRG constructions, we obtain the first
deterministic quasi-polynomial time algorithms for approximately counting the
number of solutions to a broad class of integer programs, including dense
covering problems and contingency tables.
