首页    期刊浏览 2024年12月04日 星期三
登录注册

文章基本信息

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

    This paper studies expansion properties of the (generalized) Johnson Graph. For natural numbers t < l < k, the nodes of the graph are sets of size l in a universe of size k. Two sets are connected if their intersection is of size t. The Johnson graph arises often in combinatorics and theoretical computer science: it represents a “slice” of the noisy hypercube, and it is the graph that underlies direct product tests as well as a candidate hard unique game. We prove that any small set of vertices in the graph either has near perfect edge expansion or is not pseudorandom. Here “not pseudorandom” means that the set becomes denser when conditioning on containing a small set of elements. In other words, we show that slices of the noisy hypercube – while not small set expanders like the noisy hypercube – only have non-expanding small sets of a certain simple structure. This paper is related to a recent line of work establishing the 2-to-2 Theorem in PCP. The result was motivated, in part, by [DKKMS] which hypothesized and made partial progress on similar result for the Grassmann graph. In turn, our result for the Johnson graphs served as a crucial step towards the full result for the Grassmann graphs completed subsequently in [KMS].

  • 关键词:2-to-2 Games Theorem ; expansion ; Johnson graph ; PCP
国家哲学社会科学文献中心版权所有