Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-006 | 12th January 2018 02:46

Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion

RSS-Feed




Revision #1
Authors: Subhash Khot, Dor Minzer, Muli Safra
Accepted on: 12th January 2018 02:46
Downloads: 654
Keywords: 


Abstract:

We prove that pseudorandom sets in Grassmann graph have near-perfect expansion as hypothesized in [DKKMS-2]. This completes the proof of the $2$-to-$2$ Games Conjecture (albeit with imperfect completeness) as proposed in [KMS, DKKMS-1], along with a contribution from [BKT, KMMS].

The Grassmann graph $Gr_{global}$ contains induced subgraphs $Gr_{local}$ that are themselves isomorphic to Grassmann graphs of lower orders.
A set is called pseudorandom if its density is $o(1)$ inside all subgraphs $Gr_{local}$ whose order is $O(1)$ lower than that of $Gr_{global}$. We prove that pseudorandom sets have expansion $1-o(1)$, greatly extending the results and techniques in [DKKMS-2].


Paper:

TR18-006 | 10th January 2018 01:42

Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion





TR18-006
Authors: Subhash Khot, Dor Minzer, Muli Safra
Publication: 10th January 2018 01:45
Downloads: 659
Keywords: 


Abstract:

We prove that pseudorandom sets in Grassmann graph have near-perfect expansion as hypothesized in [DKKMS-2]. This completes
the proof of the $2$-to-$2$ Games Conjecture (albeit with imperfect completeness) as proposed in [KMS, DKKMS-1], along with a
contribution from [BKT].

The Grassmann graph $Gr_{global}$ contains induced subgraphs $Gr_{local}$ that are themselves isomorphic to Grassmann graphs of lower orders.
A set is called pseudorandom if its density is $o(1)$ inside all subgraphs $Gr_{local}$ whose order is $O(1)$ lower than that of $Gr_{global}$.
We prove that pseudorandom sets have expansion $1-o(1)$, greatly extending the results and techniques in [DKKMS-2].



ISSN 1433-8092 | Imprint