Explicit Dimension Reduction and its Applications

Zohar Karnin (Ph.D. Thesis Seminar)

Wednesday, 25.05.2011, 14:30

Taub 601

Advisor: Prof. A. Shpilka

We construct a small set of explicit linear transformations mapping R^n to R^t,
where t=O(log(\gamma^{-1}) \epsilon^{-2}), such that the L_2 norm of any vector
in R^n is distorted by at most 1 \pm \epsilon in at least a fraction of
1-\gamma of the transformations in the set. Albeit the tradeoff between the size
of the set and the success probability is sub-optimal compated with probablistic
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 linear threshold functions on S^{n-1}, for \epsilon=o(1). We also use it to construct
an \epsilon-sample for digons in S^{n-1}, for \epsilon=o(1).
This construction leads to an efficient 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).
Our technique for constructing an \epsilon-sample for linear threshold functions
on the sphere is considerably different than previous techniques that rely
on k-wise independent sample spaces.