Subscribe
San Jose, California USA
June 8, 2011 to June 11, 2011
ISBN: 978-0-7695-4411-3
pp: 262-272
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.
INDEX TERMS
Sample Space, Pseudo Random Generator, PRG, Johnoson-Lindenstrauss, Dimension Reduction, Derandomization, Max-Cut, Linear Threshold Function, Halfspace, Digon
CITATION
Zohar S. Karnin, Yuval Rabani, Amir Shpilka, "Explicit Dimension Reduction and Its Applications", CCC, 2011, 2012 IEEE 27th Conference on Computational Complexity, 2012 IEEE 27th Conference on Computational Complexity 2011, pp. 262-272, doi:10.1109/CCC.2011.20
{"extraction_info": {"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8827934265136719, "perplexity": 3527.4163570593855}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2015-27/segments/1435375097475.46/warc/CC-MAIN-20150627031817-00053-ip-10-179-60-89.ec2.internal.warc.gz"}