Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Explicit Dimension Reduction and its Applications
event speaker icon
Zohar Karnin (Ph.D. Thesis Seminar)
event date icon
Wednesday, 25.05.2011, 14:30
event location icon
Taub 601
event speaker icon
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.