@incollection{Karp72,
  author = {Karp, Richard M.},
  title = {Reducibility among Combinatorial Problems},
  booktitle = {Complexity of Computer Computations},
  editor = {Miller, Raymond E. and Thatcher, James W.},
  publisher = {Plenum Press},
  address = {New York},
  pages = {85--103},
  year = {1972},
  doi = {10.1007/978-1-4684-2001-2_9},
  url = {https://doi.org/10.1007/978-1-4684-2001-2_9}
}

@article{GW95,
  author = {Goemans, Michel X. and Williamson, David P.},
  title = {Improved Approximation Algorithms for Maximum Cut and
           Satisfiability Problems Using Semidefinite Programming},
  journal = {Journal of the ACM},
  volume = {42},
  number = {6},
  pages = {1115--1145},
  year = {1995},
  doi = {10.1145/227683.227684},
  url = {https://math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf}
}

@article{Hastad01,
  author = {H{\aa}stad, Johan},
  title = {Some Optimal Inapproximability Results},
  journal = {Journal of the ACM},
  volume = {48},
  number = {4},
  pages = {798--859},
  year = {2001},
  doi = {10.1145/502090.502098},
  url = {https://www.csc.kth.se/~johanh/optimalinap.pdf}
}

@article{KKMO07,
  author = {Khot, Subhash and Kindler, Guy and Mossel, Elchanan
            and O'Donnell, Ryan},
  title = {Optimal Inapproximability Results for {MAX-CUT}
           and Other 2-Variable {CSPs}?},
  journal = {SIAM Journal on Computing},
  volume = {37},
  number = {1},
  pages = {319--357},
  year = {2007},
  doi = {10.1137/S0097539705447372},
  url = {https://www.stat.berkeley.edu/~mossel/publications/max_cut_final.pdf}
}

@article{MOO10,
  author = {Mossel, Elchanan and O'Donnell, Ryan and Oleszkiewicz, Krzysztof},
  title = {Noise Stability of Functions with Low Influences:
           Invariance and Optimality},
  journal = {Annals of Mathematics},
  volume = {171},
  number = {1},
  pages = {295--341},
  year = {2010},
  doi = {10.4007/annals.2010.171.295},
  url = {https://annals.math.princeton.edu/2010/171-1/p05}
}

@inproceedings{OW08,
  author = {O'Donnell, Ryan and Wu, Yi},
  title = {An Optimal {SDP} Algorithm for {Max-Cut}, and Equally Optimal
           Long Code Tests},
  booktitle = {Proceedings of the Fortieth Annual ACM Symposium
               on Theory of Computing},
  pages = {335--344},
  publisher = {ACM},
  year = {2008},
  doi = {10.1145/1374376.1374425},
  url = {https://dl.acm.org/doi/10.1145/1374376.1374425}
}

@inproceedings{Raghavendra08,
  author = {Raghavendra, Prasad},
  title = {Optimal Algorithms and Inapproximability Results for Every {CSP}?},
  booktitle = {Proceedings of the Fortieth Annual ACM Symposium
               on Theory of Computing},
  pages = {245--254},
  publisher = {ACM},
  year = {2008},
  doi = {10.1145/1374376.1374414},
  url = {https://dl.acm.org/doi/10.1145/1374376.1374414}
}

@article{KMS25,
  author = {Khot, Subhash and Minzer, Dor and Safra, Muli},
  title = {On Independent Sets, 2-to-2 Games and {Grassmann} Graphs},
  journal = {Theory of Computing},
  volume = {21},
  number = {10},
  pages = {1--55},
  year = {2025},
  doi = {10.4086/toc.2025.v021a010},
  url = {https://theoryofcomputing.org/articles/v021a010/v021a010.pdf},
  note = {Preliminary version in STOC 2017}
}

@article{DKKMS25,
  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},
  url = {https://theoryofcomputing.org/articles/v021a011/v021a011.pdf},
  note = {Preliminary version in STOC 2018}
}

@inproceedings{BKS19,
  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)},
  editor = {Blum, Avrim},
  series = {Leibniz International Proceedings in Informatics},
  volume = {124},
  pages = {9:1--9:12},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  year = {2019},
  doi = {10.4230/LIPIcs.ITCS.2019.9},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.9}
}

@article{KMS23,
  author = {Khot, Subhash and Minzer, Dor and Safra, Muli},
  title = {Pseudorandom Sets in {Grassmann} Graph Have Near-Perfect Expansion},
  journal = {Annals of Mathematics},
  volume = {198},
  number = {1},
  pages = {1--92},
  year = {2023},
  doi = {10.4007/annals.2023.198.1.1},
  url = {https://annals.math.princeton.edu/2023/198-1/p01}
}

@inproceedings{Khot02,
  author = {Khot, Subhash},
  title = {On the Power of Unique 2-Prover 1-Round Games},
  booktitle = {Proceedings of the Thirty-Fourth Annual ACM Symposium
               on Theory of Computing},
  pages = {767--775},
  publisher = {ACM},
  year = {2002},
  doi = {10.1145/509907.510017},
  url = {https://dl.acm.org/doi/10.1145/509907.510017}
}

@article{TSSW00,
  author = {Trevisan, Luca and Sorkin, Gregory B. and Sudan, Madhu and Williamson, David P.},
  title = {Gadgets, Approximation, and Linear Programming},
  journal = {SIAM Journal on Computing}, volume = {29}, number = {6},
  pages = {2074--2097}, year = {2000},
  doi = {10.1137/S0097539797328847},
  url = {https://doi.org/10.1137/S0097539797328847}
}

@article{FS02,
  author = {Feige, Uriel and Schechtman, Gideon},
  title = {On the Optimality of the Random Hyperplane Rounding Technique for {MAX CUT}},
  journal = {Random Structures \& Algorithms}, volume = {20}, number = {3},
  pages = {403--440}, year = {2002},
  doi = {10.1002/rsa.10036}, url = {https://doi.org/10.1002/rsa.10036}
}

@article{Borell85,
  author = {Borell, Christer},
  title = {Geometric Bounds on the {Ornstein--Uhlenbeck} Velocity Process},
  journal = {Zeitschrift f{\"u}r Wahrscheinlichkeitstheorie und Verwandte Gebiete},
  volume = {70}, number = {1}, pages = {1--13}, year = {1985},
  doi = {10.1007/BF00532234}, url = {https://doi.org/10.1007/BF00532234}
}

@article{FGLSS96,
  author = {Feige, Uriel and Goldwasser, Shafi and Lov{\'a}sz, L{\'a}szl{\'o} and Safra, Shmuel and Szegedy, Mario},
  title = {Interactive Proofs and the Hardness of Approximating Cliques},
  journal = {Journal of the ACM},
  volume = {43}, number = {2}, pages = {268--292}, year = {1996},
  doi = {10.1145/226643.226652},
  url = {https://www.cs.tau.ac.il/~safra/PapersAndTalks/FGLSS.pdf}
}

@article{AroraSafra98,
  author = {Arora, Sanjeev and Safra, Shmuel},
  title = {Probabilistic Checking of Proofs: A New Characterization of {NP}},
  journal = {Journal of the ACM},
  volume = {45}, number = {1}, pages = {70--122}, year = {1998},
  doi = {10.1145/273865.273901},
  url = {https://www.cs.umd.edu/~gasarch/TOPICS/pcp/AS.pdf},
  note = {Preliminary version in FOCS 1992}
}

@article{ALMSS98,
  author = {Arora, Sanjeev and Lund, Carsten and Motwani, Rajeev and Sudan, Madhu and Szegedy, Mario},
  title = {Proof Verification and the Hardness of Approximation Problems},
  journal = {Journal of the ACM},
  volume = {45}, number = {3}, pages = {501--555}, year = {1998},
  doi = {10.1145/278298.278306},
  url = {https://people.csail.mit.edu/madhu/papers/1992/almss-journ.pdf},
  note = {Preliminary version in FOCS 1992}
}

@article{BGS98,
  author = {Bellare, Mihir and Goldreich, Oded and Sudan, Madhu},
  title = {Free Bits, {PCPs}, and Nonapproximability---Towards Tight Results},
  journal = {SIAM Journal on Computing}, volume = {27}, number = {3},
  pages = {804--915}, year = {1998},
  doi = {10.1137/S0097539796302531},
  url = {https://doi.org/10.1137/S0097539796302531}
}