Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-077 | 23rd April 2018 21:53

Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture


Authors: Boaz Barak, Pravesh Kothari, David Steurer
Publication: 23rd April 2018 22:51
Downloads: 1086


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.

ISSN 1433-8092 | Imprint