On non-optimally expanding sets in grassmann graphs

Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We study the structure of non-expanding sets in the Grassmann graph. We put forth a hypothesis stating that every small set whose expansion is smaller than 1 − must be correlated with one of a specified list of sets which are isomorphic to smaller Grassmann graphs. We develop a framework of Fourier analysis for analyzing functions over the Grassmann graph, and prove that our hypothesis holds for all sets whose expansion is below 7/8. In the companion submitted paper [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018], the authors show that a linearity agreement hypothesis implies an NP-hardness gap of 1/2 − vs for unique games and other inapproximability results. In [Barak, Kothari and Steurer, ECCC TR18-077], the authors show that the hypothesis in this work implies the linearity agreement hypothesis of [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018]. Combined with our main theorem here this proves a version of the linearity agreement hypothesis with certain specific parameters. Short of proving the entire hypothesis, this nevertheless suffices for getting new unconditional NP hardness gaps for label cover with 2-to-1 and unique constraints. Our Expansion Hypothesis has been subsequently proved in its full form [Khot, Minzer and Safra, ECCC TR18-006] thereby proving the agreement hypothesis of [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018] and completing the proof of the 2-to-1 Games Conjecture (albeit with imperfect completeness).

Original languageEnglish (US)
Title of host publicationSTOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
EditorsMonika Henzinger, David Kempe, Ilias Diakonikolas
PublisherAssociation for Computing Machinery
Pages1193-1206
Number of pages14
ISBN (Electronic)9781450355599
DOIs
StatePublished - Jun 20 2018
Event50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States
Duration: Jun 25 2018Jun 29 2018

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other50th Annual ACM Symposium on Theory of Computing, STOC 2018
CountryUnited States
CityLos Angeles
Period6/25/186/29/18

Keywords

  • 2-to-2 games
  • Grassmann graph
  • PCP
  • Unique games

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'On non-optimally expanding sets in grassmann graphs'. Together they form a unique fingerprint.

  • Cite this

    Dinur, I., Khot, S., Kindler, G., Minzer, D., & Safra, M. (2018). On non-optimally expanding sets in grassmann graphs. In M. Henzinger, D. Kempe, & I. Diakonikolas (Eds.), STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (pp. 1193-1206). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3188745.3188806