首页    期刊浏览 2025年02月19日 星期三
登录注册

文章基本信息

  • 标题:Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion
  • 本地全文:下载
  • 作者:Subhash Khot ; Dor Minzer ; Muli Safra
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2018
  • 卷号:2018
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We prove that pseudorandom sets in Grassmann graph have near-perfect expansion as hypothesized in [DKKMS-2]. This completes the proof of the 2 -to- 2 Games Conjecture (albeit with imperfect completeness) as proposed in [KMS, DKKMS-1], along with a contribution from [BKT].

    The Grassmann graph G r globa l contains induced subgraphs G r loca l that are themselves isomorphic to Grassmann graphs of lower orders. A set is called pseudorandom if its density is o (1) inside all subgraphs G r loca l whose order is O (1) lower than that of G r globa l . We prove that pseudorandom sets have expansion 1 − o (1) , greatly extending the results and techniques in [DKKMS-2].

国家哲学社会科学文献中心版权所有