Name
Abstract | ||
|---|---|---|
We construct a small set of explicit linear transformationsmapping R^n to R^t, where t=O(log (\gamma^{-1}) \eps^{-2} ), suchthat the L_2 norm of any vector in R^n is distorted by atmost 1\pm \eps in at least a fraction of 1-\gamma of thetransformations in the set. Albeit the tradeoff between thesize of the set and the success probability is sub-optimal comparedwith probabilistic arguments, we nevertheless are able to applyour construction to a number of problems. In particular, we use itto construct an \eps-sample (or pseudo-random generator) forlinear threshold functions on S^{n-1}, for \eps = o(1). Wealso use it to construct an \eps-sample for spherical digons inS^{n-1}, for \eps=o(1). This construction leads to anefficient oblivious derandomization of the Goemans-Williamson MAXCUT algorithm and similar approximation algorithms (i.e., weconstruct a small set of hyperplanes, such that for any instancewe can choose one of them to generate a good solution). Our technique for constructing \eps-sample for linear thresholdfunctions on the sphere is considerably different than previoustechniques that rely on k-wise independent sample spaces. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1137/110828812 | SIAM Journal on Computing |
Keywords | DocType | Volume |
dimension reduction,pseudorandom generator,max cut | Conference | 41 |
Issue | ISSN | Citations |
1 | 1093-0159 | 10 |
PageRank | References | Authors |
0.59 | 26 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zohar S. Karnin | 1 | 266 | 20.98 |
| Yuval Rabani | 2 | 2265 | 274.98 |
| Amir Shpilka | 3 | 1095 | 64.27 |