Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > INTEGER PROGRAMS:
Reports tagged with Integer Programs:
TR09-144 | 24th December 2009
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 ... more >>>