Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with convex sets:
TR07-037 | 2nd February 2007
Leonid Gurvits

Polynomial time algorithms to approximate mixed volumes within a simply exponential factor

Revisions: 1

We study in this paper randomized algorithms to approximate the mixed volume of well-presented convex compact sets.
Our main result is a poly-time algorithm which approximates $V(K_1,...,K_n)$ with multiplicative error $e^n$ and
with better rates if the affine dimensions of most of the sets $K_i$ are small.\\
Our approach is ... more >>>

TR09-144 | 24th December 2009
Prahladh Harsha, Adam Klivans, Raghu Meka

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 ... more >>>

ISSN 1433-8092 | Imprint