Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > 2-TO-2 GAME CONJECTURE:
Reports tagged with 2-to-2 Game Conjecture:
TR18-006 | 10th January 2018
Subhash Khot, Dor Minzer, Muli Safra

Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion

Revisions: 2

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 ... more >>>




ISSN 1433-8092 | Imprint