ECCC-Report TR17-094https://eccc.weizmann.ac.il/report/2017/094Comments and Revisions published for TR17-094en-usThu, 25 May 2017 09:06:33 +0300
Paper TR17-094
| On Non-Optimally Expanding Sets in Grassmann Graphs |
Irit Dinur,
Subhash Khot,
Guy Kindler,
Dor Minzer,
Muli Safra
https://eccc.weizmann.ac.il/report/2017/094The paper investigates expansion properties of the Grassmann graph,
motivated by recent results of [KMS, DKKMS] concerning hardness
of the Vertex-Cover and of the $2$-to-$1$ Games problems. Proving the
hypotheses put forward by these papers seems to first require a better
understanding of these expansion properties.
We consider the edge expansion of small sets, which is the probability of choosing a random vertex in the set and traversing a random edge touching it, and landing outside the set.
A random small set of vertices has edge expansion nearly $1$ with high probability. However, some sets in the Grassmann graph have strictly smaller edge expansion.
We present a hypothesis that proposes a characterization of such sets: any such set must be denser inside subgraphs that are
by themselves (isomorphic to) smaller Grassmann graphs. We say that
such a set is *non-pseudorandom*. We achieve
partial progress towards this hypothesis, proving that sets whose
expansion is strictly smaller than $7/8$ are non-pseudorandom.
This is achieved through a spectral approach, showing that Boolean valued functions
over the Grassmann graph that have significant correlation with eigenspaces corresponding to the
top two non-trivial eigenvalues (that are approximately $1/2$ and $1/4$) must be non-pseudorandom.Thu, 25 May 2017 09:06:33 +0300https://eccc.weizmann.ac.il/report/2017/094