首页    期刊浏览 2024年07月05日 星期五
登录注册

文章基本信息

  • 标题:Explicit Dimension Reduction and Its Applications
  • 本地全文:下载
  • 作者:Zohar Karnin ; Yuval Rabani ; Amir Shpilka
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2009
  • 卷号:2009
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We construct a small set of explicit linear transformations mapping Rn to RO(logn), such that the L2 norm ofany vector in Rn is distorted by at most 1o(1) in atleast a fraction of 1−o(1) of the transformations in the set.Albeit the tradeoff between the distortion and the successprobability is sub-optimal compared with probabilistic arguments,we nevertheless are able to apply our construction to a number ofproblems. In particular, we use it to construct an -sample(or pseudo-random generator) for spherical digons in Sn−1,for =o(1). This construction leads to an obliviousderandomization of the Goemans-Williamson MAX CUT algorithm andsimilar approximation algorithms (i.e., we construct a small setof hyperplanes, such that for any instance we can choose one ofthem to generate a good solution). We also construct an-sample for linear threshold functions on Sn−1, for=o(1).

  • 关键词:derandomization; epsilon-sample; explicit construction; Johnson-Lindenstrauss Lemma; linear threshold function
国家哲学社会科学文献中心版权所有