Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-144 | 24th December 2009 17:46

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
$$\left|\Pr\left[X \in P\right] - \Pr\left[Y \in P\right]\right| \leq \log^{8/5}k \cdot \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:

\item A bound of $\log^{O(1)}k \cdot {\epsilon}^{1/6}$ on the Boolean noise
sensitivity of intersections of $k$ ``regular'' halfspaces (previous
work 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(\log n\,\poly(\log k,1/\delta))$ that $\delta$-fools {\em 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.

ISSN 1433-8092 | Imprint