Small-set expansion in shortcode graph and the 2-to-2 conjecture

TY - GEN

T1 - Small-set expansion in shortcode graph and the 2-to-2 conjecture

AU - Barak, Boaz

AU - Kothari, Pravesh K.

AU - Steurer, David

N1 - Publisher Copyright: © Boaz Barak, Pravesh K. Kothari, and David Steurer.

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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 soundness of Grassmannian agreement tester follows from a conjecture we call the “Shortcode Expansion Hypothesis” characterizing the non-expanding sets of the degree-two Short code 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 “Shortcode Expansion 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. We believe that the Shortcode graph provides a useful view of both the hypothesis and the reduction, and might be suitable for obtaining new hardness reductions.

AB - 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 soundness of Grassmannian agreement tester follows from a conjecture we call the “Shortcode Expansion Hypothesis” characterizing the non-expanding sets of the degree-two Short code 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 “Shortcode Expansion 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. We believe that the Shortcode graph provides a useful view of both the hypothesis and the reduction, and might be suitable for obtaining new hardness reductions.

KW - Grassmann Graph

KW - Shortcode

KW - Small-Set Expansion

KW - Unique Games Conjecture

UR - http://www.scopus.com/inward/record.url?scp=85069442776&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85069442776&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ITCS.2019.9

DO - 10.4230/LIPIcs.ITCS.2019.9

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 10th Innovations in Theoretical Computer Science, ITCS 2019

A2 - Blum, Avrim

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 10th Innovations in Theoretical Computer Science, ITCS 2019

Y2 - 10 January 2019 through 12 January 2019

ER -