ECCC-Report TR09-121https://eccc.weizmann.ac.il/report/2009/121Comments and Revisions published for TR09-121en-usSun, 22 Nov 2009 13:55:22 +0200
Paper TR09-121
| Explicit Dimension Reduction and Its Applications |
Zohar Karnin,
Yuval Rabani,
Amir Shpilka
https://eccc.weizmann.ac.il/report/2009/121We 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)$.Sun, 22 Nov 2009 13:55:22 +0200https://eccc.weizmann.ac.il/report/2009/121