Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR09-144 | 24th December 2009 17:46

An Invariance Principle for Polytopes

RSS-Feed

Abstract:

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:

\begin{itemize}
\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.
\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.



ISSN 1433-8092 | Imprint