@inproceedings{d3f10ec092a9489b819013574cae1096,

title = "On Independent Sets, 2-to-2 Games, and Grassmann Graphs",

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).",

keywords = "PCP, Unique games, Vertex-Cover",

author = "Subhash Khot and Dor Minzer and Muli Safra",

year = "2017",

month = jun,

day = "19",

doi = "10.1145/3055399.3055432",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "576--589",

editor = "Pierre McKenzie and Valerie King and Hamed Hatami",

booktitle = "STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing",

note = "49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 ; Conference date: 19-06-2017 Through 23-06-2017",

}