ECCC-Report TR18-006https://eccc.weizmann.ac.il/report/2018/006Comments and Revisions published for TR18-006en-usSat, 19 May 2018 14:13:04 +0300
Revision 2
| Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion |
Subhash Khot,
Dor Minzer,
Muli Safra
https://eccc.weizmann.ac.il/report/2018/006#revision2We 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].Sat, 19 May 2018 14:13:04 +0300https://eccc.weizmann.ac.il/report/2018/006#revision2
Revision 1
| Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion |
Subhash Khot,
Dor Minzer,
Muli Safra
https://eccc.weizmann.ac.il/report/2018/006#revision1We 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].Fri, 12 Jan 2018 02:46:12 +0200https://eccc.weizmann.ac.il/report/2018/006#revision1
Paper TR18-006
| Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion |
Subhash Khot,
Dor Minzer,
Muli Safra
https://eccc.weizmann.ac.il/report/2018/006We 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].Wed, 10 Jan 2018 01:45:48 +0200https://eccc.weizmann.ac.il/report/2018/006