Fetching the paper…

Reading the bibliography…

2018

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

Barak, Boaz, Kothari, Pravesh K., Steurer, David

Original
PDF
Post on X

Understand

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.

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

Built on

Subhash Khot, On the power of unique 2-prover 1-round games , Proceedings of the 17th Annual IEEE Conference on Computational Complexity, Montréal, Québec, Canada, May 21-24, 2002, 2002, p. 25
2002
Earlier work this paper cites.
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, and David Steurer, Making the long code shorter , SIAM J. Comput. 44
2015
Earlier work this paper cites.

Similar

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
2016
Cited alongside, same era.
Mitali Bafna, Chi-Ning Chou, and Zhao Song, An exposition of dinur-khot-kindler-minzer-safra proof for the 2-to-2 games conjecture , http://boazbarak.org/dkkmsnotes.pdf
Cited in the paper.

Then

Subhash Khot, Dor Minzer, and Muli Safra, On independent sets, 2-to-2 games, and grassmann graphs , Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, 2017, pp. 576–589
2017
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…