TR09-144 Authors: Prahladh Harsha, Adam Klivans, Raghu Meka

Publication: 24th December 2009 18:17

Downloads: 3075

Keywords:

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.