Let X be randomly chosen from −11n , and let Y be randomlychosen from the standard spherical Gaussian on \Rn. For any (possibly unbounded) polytope Pformed by the intersection of k halfspaces, we prove that PrXP−PrYPlog85k where isa 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:

\begin{itemize}\item A bound of logO(1)k16 on the Boolean noisesensitivity of intersections of k ``regular'' halfspaces (previouswork gave bounds linear in k). This gives a corresponding agnostic learning algorithm for intersections of regular halfspaces.\item A pseudorandom generator (PRG) with seed length O(logn\poly(logk1)) that -fools {\em all} polytopes with k faces with respect to the Gaussian distribution. \end{itemize}

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.