On Independent Sets, 2-to-2 Games, and Grassmann Graphs

Subhash Khot, Dor Minzer, Muli Safra

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

Abstract

We present a candidate reduction from the 3-Lin problem to the 2-to-2 Games problem and present a combinatorial hypothesis about Grassmann graphs which, if correct, is sufficient to show the soundness of the reduction in a certain non-standard sense. A reduction that is sound in this non-standard sense implies that it is NP-hard to distinguish whether an n-vertex graph has an independent set of size (1-1/√2)n-o(n) or whether every independent set has size o(n), and consequently, that it is NP-hard to approximate the Vertex Cover problem within a factor √2-o(1).

Original languageEnglish (US)
Title of host publicationSTOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
EditorsPierre McKenzie, Valerie King, Hamed Hatami
PublisherAssociation for Computing Machinery
Pages576-589
Number of pages14
ISBN (Electronic)9781450345286
DOIs
StatePublished - Jun 19 2017
Event49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 - Montreal, Canada
Duration: Jun 19 2017Jun 23 2017

Publication series

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

Other

Other49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017
CountryCanada
CityMontreal
Period6/19/176/23/17

Keywords

  • PCP
  • Unique games
  • Vertex-Cover

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'On Independent Sets, 2-to-2 Games, and Grassmann Graphs'. Together they form a unique fingerprint.

Cite this