@inproceedings{c4042c34fe1c49aea21fbde6aa4ff407,
title = "Pseudorandom sets in Grassmann graph have near-perfect expansion",
abstract = "We prove that pseudorandom sets in the Grassmann graph have near-perfect expansion. This completes the last missing piece of the proof of the 2-to-2-Games Conjecture (albeit with imperfect completeness). The Grassmann graph has induced subgraphs that are themselves isomorphic to Grassmann graphs of lower orders. A set of vertices is called pseudorandom if its density within all such subgraphs (of constant order) is at most slightly higher than its density in the entire graph. We prove that pseudorandom sets have almost no edges within them. Namely, their edge-expansion is very close to 1.",
keywords = "2-to-2 games, Grassmann graph, PCP, Unique games conjecture",
author = "Subhash Khot and Dor Minzer and Muli Safra",
note = "Funding Information: Author Khot was supported by NSF grant CCF-1422159, Simons Collaboration on Algorithms and Geometry, and Simons Investigator Award. Author Minzer was supported by Clore Fellowship, ISF grant 2013/17, BSF grant 2016414 and Blavatnik fund. Author Safra was supported by ISF grant 2013/17, BSF grant 2016414 and Blavatnik fund. Funding Information: Our most sincere thanks to Boaz Barak, Irit Dinur, Yuval Filmus, Guy Kindler, Pravesh Kothari, Dana Moshkovitz, Prasad Raghavendra, Ran Raz, and David Steurer for several discussions and collaborations that led to this work. Author Khot was supported by NSF grant CCF-1422159, Simons Collaboration on Algorithms and Geometry, and Simons Investigator Award. Author Minzer was supported by Clore Fellowship, ISF grant 2013/17, BSF grant 2016414 and Blavatnik fund. Author Safra was supported by ISF grant 2013/17, BSF grant 2016414 and Blavatnik fund. Publisher Copyright: {\textcopyright} 2018 IEEE.; 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 ; Conference date: 07-10-2018 Through 09-10-2018",
year = "2018",
month = nov,
day = "30",
doi = "10.1109/FOCS.2018.00062",
language = "English (US)",
series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",
publisher = "IEEE Computer Society",
pages = "592--601",
editor = "Mikkel Thorup",
booktitle = "Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018",
}