ECCC-Report TR09-144https://eccc.weizmann.ac.il/report/2009/144Comments and Revisions published for TR09-144en-usThu, 24 Dec 2009 18:17:42 +0200
Paper TR09-144
| An Invariance Principle for Polytopes |
Prahladh Harsha,
Adam Klivans,
Raghu Meka
https://eccc.weizmann.ac.il/report/2009/144 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. Thu, 24 Dec 2009 18:17:42 +0200https://eccc.weizmann.ac.il/report/2009/144