Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion

by Subhash Khot, Dor Minzer, and Muli Safra

Oded's comments

This is a great result (or rather a result that has great consequences).

It is quite odd that the abstract and introduction of this paper do not offer a decent survey of the consequences of the main result, let alone the weird idea of listing consequences and supporting the main result in appendices (see Apdx B and C, resp.). Fortunately, Boaz Barak did the work for us (wrt the onsequences). Hence, let me refer you to Boaz's account. [And Goethe said Why should I write this scene anew, given that Lord Byron wrote it so well?]

In my opinion, the establishment of intermediate hardness for UGC[0.4999,0.001] is the most fascinating aspect of the paper: It is fascinating both per se and per casting concrete doubts on the claim that the known algorithms for UGC provide evidence that the UGC conjecture is wrong. Let me only highlight yet another consequence: The $sqrt 2$-factor NP-hardness for Vertex Cover.

(Like many others, when faced with the best algorithms for the UG problem, I thought to myself that it may well be the case that this problem has subexponential complexity with the exponent depending on the error parameter. But I first heard this conjecture stated aloud as a positive possibility by Johan, although it was in a private discussion.)

The original 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].

See ECCC TR18-006.


Back to list of Oded's choices.