@article{DKKMS2025, author = {Dinur, Irit and Khot, Subhash and Kindler, Guy and Minzer, Dor and Safra, Muli}, title = {Towards a Proof of the {2-to-1 Games Conjecture}?}, journal = {Theory of Computing}, volume = {21}, number = {11}, pages = {1--50}, year = {2025}, doi = {10.4086/toc.2025.v021a011}, note = {\url{https://doi.org/10.4086/toc.2025.v021a011}}, url = {https://theoryofcomputing.org/articles/v021a011/v021a011.pdf} } @techreport{KMS2018, author = {Khot, Subhash and Minzer, Dor and Safra, Muli}, title = {Pseudorandom Sets in {Grassmann} Graph have Near-Perfect Expansion}, institution = {Electronic Colloquium on Computational Complexity}, number = {TR18-006}, year = {2018}, note = {Revision 2, May 19, 2018. \url{https://eccc.weizmann.ac.il/report/2018/006/revision/2/download}}, url = {https://eccc.weizmann.ac.il/report/2018/006/revision/2/download} } @inproceedings{BKS2019, author = {Barak, Boaz and Kothari, Pravesh K. and Steurer, David}, title = {Small-Set Expansion in Shortcode Graph and the {2-to-2 Conjecture}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, volume = {124}, pages = {9:1--9:12}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, year = {2019}, doi = {10.4230/LIPIcs.ITCS.2019.9}, note = {\url{https://doi.org/10.4230/LIPIcs.ITCS.2019.9}}, url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.9} } @article{Friedgut1998, author = {Friedgut, Ehud}, title = {{Boolean} Functions With Low Average Sensitivity Depend On Few Coordinates}, journal = {Combinatorica}, volume = {18}, number = {1}, pages = {27--35}, year = {1998}, doi = {10.1007/PL00009809}, note = {\url{https://doi.org/10.1007/PL00009809}}, url = {https://link.springer.com/article/10.1007/PL00009809} } @article{Ramsey1930, author = {Ramsey, F. P.}, title = {On a Problem of Formal Logic}, journal = {Proceedings of the London Mathematical Society}, series = {2}, volume = {s2-30}, number = {1}, pages = {264--286}, year = {1930}, doi = {10.1112/plms/s2-30.1.264}, note = {\url{https://doi.org/10.1112/plms/s2-30.1.264}}, url = {https://academic.oup.com/plms/article-abstract/s2-30/1/264/1589296} } @article{vonNeumann1928, author = {von Neumann, J.}, title = {Zur {Theorie} der {Gesellschaftsspiele}}, journal = {Mathematische Annalen}, volume = {100}, number = {1}, pages = {295--320}, year = {1928}, doi = {10.1007/BF01448847}, note = {\url{https://doi.org/10.1007/BF01448847}}, url = {https://link.springer.com/article/10.1007/BF01448847} } @article{Seymour1995, author = {Seymour, P. D.}, title = {Packing directed circuits fractionally}, journal = {Combinatorica}, volume = {15}, number = {2}, pages = {281--288}, year = {1995}, doi = {10.1007/BF01200760}, note = {\url{https://doi.org/10.1007/BF01200760}}, url = {https://link.springer.com/article/10.1007/BF01200760} } @article{Even1998, author = {Even, G. and Naor, J. and Schieber, B. and Sudan, M.}, title = {Approximating minimum feedback sets and multicuts in directed graphs}, journal = {Algorithmica}, volume = {20}, number = {2}, pages = {151--174}, year = {1998}, doi = {10.1007/PL00009191}, note = {\url{https://doi.org/10.1007/PL00009191}}, url = {https://link.springer.com/article/10.1007/PL00009191} } @article{DinurSafra2005, author = {Dinur, Irit and Safra, Samuel}, title = {On the hardness of approximating minimum vertex cover}, journal = {Annals of Mathematics}, volume = {162}, number = {1}, pages = {439--485}, year = {2005}, doi = {10.4007/annals.2005.162.439}, note = {\url{https://doi.org/10.4007/annals.2005.162.439}}, url = {https://annals.math.princeton.edu/wp-content/uploads/annals-v162-n1-p08.pdf} } @article{Svensson2013, author = {Svensson, Ola}, title = {Hardness of Vertex Deletion and Project Scheduling}, journal = {Theory of Computing}, volume = {9}, number = {24}, pages = {759--781}, year = {2013}, doi = {10.4086/toc.2013.v009a024}, note = {\url{https://doi.org/10.4086/toc.2013.v009a024}}, url = {https://theoryofcomputing.org/articles/v009a024/} } @article{GuruswamiLee2016, author = {Guruswami, Venkatesan and Lee, Euiwoong}, title = {Simple Proof of Hardness of Feedback Vertex Set}, journal = {Theory of Computing}, volume = {12}, number = {6}, pages = {1--11}, year = {2016}, doi = {10.4086/toc.2016.v012a006}, note = {\url{https://doi.org/10.4086/toc.2016.v012a006}}, url = {https://theoryofcomputing.org/articles/v012a006/} } @inproceedings{GhorbaniMnich2026, author = {Ghorbani, Ebrahim and Mnich, Matthias}, title = {A {9/4}-Approximation for Directed Feedback Vertex Sets in Quasi-Transitive Digraphs}, booktitle = {53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, volume = {374}, pages = {96:1--96:16}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, year = {2026}, doi = {10.4230/LIPIcs.ICALP.2026.96}, note = {\url{https://doi.org/10.4230/LIPIcs.ICALP.2026.96}}, url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.96} } @article{GHMRC2011, author={Guruswami, Venkatesan and H{\aa}stad, Johan and Manokaran, Rajsekar and Raghavendra, Prasad and Charikar, Moses}, title={Beating the Random Ordering Is Hard: Every Ordering {CSP} Is Approximation Resistant}, journal={SIAM Journal on Computing}, volume={40}, number={3}, pages={878--914}, year={2011}, doi={10.1137/090756144}, note={\url{https://doi.org/10.1137/090756144}} } @inproceedings{GMR2008, author={Guruswami, Venkatesan and Manokaran, Rajsekar and Raghavendra, Prasad}, title={Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph}, booktitle={49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008)}, pages={573--582}, year={2008}, publisher={IEEE}, doi={10.1109/FOCS.2008.51}, note={\url{https://doi.org/10.1109/FOCS.2008.51}} }