Small-set expansion in the short-code graph and the 2-to-2 games conjecture

with Boaz Barak, Pravesh Kothari. ITCS 2019.

PDF

abstract

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 on 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 our “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.

keywords

  • Unique Games Conjecture
  • small-set expansion
  • hardness of approximation