@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",

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

note = "59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 ; Conference date: 07-10-2018 Through 09-10-2018",

}