Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-121 | 22nd November 2009 13:54

Explicit Dimension Reduction and Its Applications



We construct a small set of explicit linear transformations mapping $R^n$ to $R^{O(\log n)}$, such that the $L_2$ norm of
any vector in $R^n$ is distorted by at most $1\pm o(1)$ in at
least a fraction of $1 - o(1)$ of the transformations in the set.
Albeit the tradeoff between the distortion and the success
probability is sub-optimal compared with probabilistic arguments,
we nevertheless are able to apply our construction to a number of
problems. In particular, we use it to construct an $\epsilon$-sample
(or pseudo-random generator) for spherical digons in $S^{n-1}$,
for $\epsilon = o(1)$. This construction leads to an oblivious
derandomization of the Goemans-Williamson MAX CUT algorithm and
similar approximation algorithms (i.e., we construct a small set
of hyperplanes, such that for any instance we can choose one of
them to generate a good solution). We also construct an
$\epsilon$-sample for linear threshold functions on $S^{n-1}$, for
$\epsilon = o(1)$.

ISSN 1433-8092 | Imprint