Dinur, Khot, Kindler, Minzer and Safra (2016) recently showed that the (imperfect completeness variant of) Khot's 2 to 2 games conjecture follows from a combinatorial hypothesis about the soundness of a certain ``Grassmanian agreement tester''. In this work, we show that the hypothesis of Dinur et al follows from a conjecture we call the ``Inverse Shortcode Hypothesis'' characterizing the non-expanding sets of the degree-two shortcode graph. We also show the latter conjecture is equivalent to a characterization of the non-expanding sets in the Grassman graph, as hypothesized by a follow-up paper of Dinur et. al. (2017).Following our work, Khot, Minzer, and Safra (2018) proved the ``Inverse Shortcode Hypothesis''. Combining their proof with our result and the reduction of Dinur et. al. (2016) completes the proof of the 2 to 2 conjecture with imperfect completeness. Moreover, we believe that the shortcode graph provides a useful view of both the hypothesis and the reduction, and might be useful in extending it further.
展开▼
