TR09-121 Authors: Zohar Karnin, Yuval Rabani, Amir Shpilka

Publication: 22nd November 2009 13:55

Downloads: 3642

Keywords:

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)$.