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

Authors Boaz Barak, Pravesh K. Kothari, David Steurer



PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.9.pdf
  • Filesize: 498 kB
  • 12 pages

Document Identifiers

Author Details

Boaz Barak
  • Harvard University School of Engineering and Applied Sciences, Cambridge, USA
Pravesh K. Kothari
  • Princeton University and IAS Princeton, USA
David Steurer
  • ETH Zurich, Zurich, Switzerland

Cite AsGet BibTex

Boaz Barak, Pravesh K. Kothari, and David Steurer. Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ITCS.2019.9

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 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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Unique Games Conjecture
  • Small-Set Expansion
  • Grassmann Graph
  • Shortcode

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Mitali Bafna, Chi-Ning Chou, and Zhao Song. An Exposition of Dinur-Khot-Kindler-Minzer-Safra Proof for the 2-to-2 Games Conjecture, 2018. URL: http://boazbarak.org/dkkmsnotes.pdf.
  2. Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, and David Steurer. Making the long code shorter. SIAM J. Comput., 44(5):1287-1324, 2015. URL: http://dx.doi.org/10.1137/130929394.
  3. Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. Towards a Proof of the 2-to-1 Games Conjecture? Electronic Colloquium on Computational Complexity (ECCC), 23:198, 2016. URL: http://eccc.hpi-web.de/report/2016/198.
  4. Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. On Non-Optimally Expanding Sets in Grassmann Graphs. STOC, 24:94, 2018. Google Scholar
  5. Subhash Khot. On the Power of Unique 2-Prover 1-Round Games. In Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002, page 25, 2002. URL: http://dx.doi.org/10.1109/CCC.2002.1004334.
  6. Subhash Khot, Dor Minzer, and Muli Safra. On independent sets, 2-to-2 games, and Grassmann graphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 576-589, 2017. URL: http://dx.doi.org/10.1145/3055399.3055432.
  7. Subhash Khot, Dor Minzer, and Muli Safra. Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion. Electronic Colloquium on Computational Complexity (ECCC), 25:6, 2018. URL: https://eccc.weizmann.ac.il/report/2018/006.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail