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