@inproceedings{Khot2002,
  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},
  series    = {STOC '02},
  pages     = {767--775},
  publisher = {Association for Computing Machinery},
  year      = {2002},
  doi       = {10.1145/509907.510017},
  note      = {\url{https://doi.org/10.1145/509907.510017}}
}

@article{Dinur2007,
  author    = {Dinur, Irit},
  title     = {The {PCP} Theorem by Gap Amplification},
  journal   = {Journal of the ACM},
  volume    = {54},
  number    = {3},
  articleno = {12},
  numpages  = {44},
  year      = {2007},
  month     = jun,
  doi       = {10.1145/1236457.1236459},
  note      = {Article 12, 44 pages. Definition 8.1 and Theorem 8.1 are cited in the author manuscript dated February 13, 2007, p.~27: \url{https://www.wisdom.weizmann.ac.il/~dinuri/mypapers/combpcp.pdf}}
}

@inproceedings{DinurSteurer2014,
  author    = {Dinur, Irit and Steurer, David},
  title     = {Analytical Approach to Parallel Repetition},
  booktitle = {Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing},
  series    = {STOC '14},
  pages     = {624--633},
  publisher = {Association for Computing Machinery},
  year      = {2014},
  doi       = {10.1145/2591796.2591884},
  note      = {Corollary 1.2 and Sections 2.1--2.2 are cited in the author manuscript dated June 10, 2014: \url{https://www.dsteurer.org/paper/productgames.pdf}}
}

@inproceedings{DinurKhotKindlerMinzerSafra2018,
  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?},
  booktitle = {Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing},
  series    = {STOC 2018},
  pages     = {376--389},
  publisher = {Association for Computing Machinery},
  year      = {2018},
  doi       = {10.1145/3188745.3188804},
  note      = {\url{https://doi.org/10.1145/3188745.3188804}. Full version: Theory of Computing 21(11):1--50, 2025, \url{https://doi.org/10.4086/toc.2025.v021a011}}
}

@inproceedings{BarakKothariSteurer2018,
  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},
  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},
  note      = {First circulated in 2018. Lemma 2.3 and Section 3 are cited in arXiv version 1: \url{https://arxiv.org/abs/1804.08662v1}}
}

@article{KhotMinzerSafra2018,
  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},
  note      = {Theorem 1.12 is cited in ECCC TR18-006, revision 2, 2018: \url{https://eccc.weizmann.ac.il/report/2018/006/revision/2/download/}}
}

@techreport{FeiMinzerWang2026,
  author      = {Fei, Yumou and Minzer, Dor and Wang, Shuo},
  title       = {On the Hardness of 4-to-1 Games with Perfect Completeness},
  institution = {Electronic Colloquium on Computational Complexity},
  type        = {Report},
  number      = {TR26-179},
  year        = {2026},
  month       = sep,
  note        = {September 14, 2026. \url{https://eccc.weizmann.ac.il/report/2026/179/}}
}


@article{AroraSafra1998,
  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},
  note = {Preliminary version in FOCS 1992. \url{https://doi.org/10.1145/273865.273901}}
}
@article{AroraLundMotwaniSudanSzegedy1998,
  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},
  note = {Preliminary version in FOCS 1992. \url{https://doi.org/10.1145/278298.278306}}
}
@article{Raz1998,
  author = {Raz, Ran}, title = {A Parallel Repetition Theorem},
  journal = {SIAM Journal on Computing}, volume = {27}, number = {3},
  pages = {763--803}, year = {1998}, doi = {10.1137/S0097539795280895},
  note = {Preliminary version in STOC 1995. \url{https://doi.org/10.1137/S0097539795280895}}
}
@article{Holenstein2009,
  author = {Holenstein, Thomas},
  title = {Parallel Repetition: Simplification and the No-Signaling Case},
  journal = {Theory of Computing}, volume = {5}, number = {8},
  pages = {141--172}, year = {2009}, doi = {10.4086/toc.2009.v005a008},
  note = {\url{https://doi.org/10.4086/toc.2009.v005a008}}
}
@article{Rao2011,
  author = {Rao, Anup},
  title = {Parallel Repetition in Projection Games and a Concentration Bound},
  journal = {SIAM Journal on Computing}, volume = {40}, number = {6},
  pages = {1871--1891}, year = {2011}, doi = {10.1137/080734042},
  note = {Preliminary version in STOC 2008. \url{https://doi.org/10.1137/080734042}}
}
@article{BellareGoldreichSudan1998,
  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},
  note = {Preliminary version in FOCS 1995. \url{https://doi.org/10.1137/S0097539796302531}}
}
@article{AustrinODonnellTanWright2014,
  author = {Austrin, Per and O'Donnell, Ryan and Tan, Li-Yang and Wright, John},
  title = {New {NP}-Hardness Results for 3-Coloring and 2-to-1 Label Cover},
  journal = {ACM Transactions on Computation Theory},
  volume = {6}, number = {1}, articleno = {2}, pages = {2:1--2:20},
  year = {2014},
  note = {Theorem 1.3 is cited in the author manuscript dated July 16, 2013: \url{https://www.cs.cmu.edu/afs/cs/Web/People/jswright/papers/coloring.pdf}}
}
@article{KhotMinzerSafra2017,
  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},
  note = {First circulated as ECCC TR16-124 in 2016; preliminary version in STOC 2017. \url{https://doi.org/10.4086/toc.2025.v021a010}}
}
@article{DinurKhotKindlerMinzerSafra2021,
  author = {Dinur, Irit and Khot, Subhash and Kindler, Guy and Minzer, Dor and Safra, Muli},
  title = {On Non-Optimally Expanding Sets in {Grassmann} Graphs},
  journal = {Israel Journal of Mathematics}, volume = {243}, number = {1},
  pages = {377--420}, year = {2021}, doi = {10.1007/s11856-021-2164-7},
  note = {First circulated as ECCC TR17-094 in 2017; preliminary version in STOC 2018. \url{https://doi.org/10.1007/s11856-021-2164-7}}
}

@inproceedings{GoldreichLevin1989,
  author = {Goldreich, Oded and Levin, Leonid A.},
  title = {A Hard-Core Predicate for All One-Way Functions},
  booktitle = {Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing},
  pages = {25--32}, publisher = {Association for Computing Machinery}, year = {1989},
  note = {Author manuscript: \url{https://www.cs.bu.edu/fac/lnd/pdf/hard.pdf}}
}
@article{NaorNaor1993,
  author = {Naor, Joseph and Naor, Moni},
  title = {Small-Bias Probability Spaces: Efficient Constructions and Applications},
  journal = {SIAM Journal on Computing}, volume = {22}, number = {4},
  pages = {838--856}, year = {1993}, doi = {10.1137/0222053},
  note = {\url{https://doi.org/10.1137/0222053}}
}
@inproceedings{BravermanKhotMinzer2021,
  author = {Braverman, Mark and Khot, Subhash and Minzer, Dor},
  title = {On Rich 2-to-1 Games},
  booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  series = {Leibniz International Proceedings in Informatics},
  volume = {185}, pages = {27:1--27:20}, year = {2021},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  doi = {10.4230/LIPIcs.ITCS.2021.27},
  note = {\url{https://doi.org/10.4230/LIPIcs.ITCS.2021.27}}
}

@article{GuruswamiSinop2013,
  author = {Guruswami, Venkatesan and Sinop, Ali Kemal},
  title = {Improved Inapproximability Results for Maximum {$k$}-Colorable Subgraph},
  journal = {Theory of Computing},
  volume = {9}, number = {11}, pages = {413--435}, year = {2013},
  doi = {10.4086/toc.2013.v009a011},
  note = {\url{https://theoryofcomputing.org/articles/v009a011/v009a011.pdf}}
}

@inproceedings{ODonnellWu2008,
  author = {O'Donnell, Ryan and Wu, Yi},
  title = {Conditional Hardness for Satisfiable {3-CSPs}},
  booktitle = {Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing},
  series = {STOC '09},
  pages = {493--502},
  publisher = {Association for Computing Machinery},
  year = {2009},
  doi = {10.1145/1536414.1536482},
  note = {Theorem 2.1 and Corollary 2.2 are cited in the author manuscript dated November 17, 2008: \url{https://www.cs.cmu.edu/~odonnell/papers/3bit-hardness.pdf}}
}

@inproceedings{GuruswamiSandeep2020,
  author = {Guruswami, Venkatesan and Sandeep, Sai},
  title = {{$d$}-to-{$1$} Hardness of Coloring {$3$}-Colorable Graphs with {$O(1)$} Colors},
  booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  series = {Leibniz International Proceedings in Informatics},
  volume = {168}, pages = {62:1--62:12}, year = {2020},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  doi = {10.4230/LIPIcs.ICALP.2020.62},
  note = {Theorem 1. \href{https://doi.org/10.4230/LIPIcs.ICALP.2020.62}{Published paper}}
}

@misc{OpenAIIndependentSets2026,
  author = {{OpenAI}},
  title = {{Hardness of finding large independent sets in three-colorable graphs}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Hardness-of-finding-large-independent-sets-in-three-colorable-graphs-September-24-2026/Hardness-of-finding-large-independent-sets-in-three-colorable-graphs-September-24-2026.pdf}{OAI:Hardness-of-finding-large-independent-sets-in-three-colorable-graphs-September-24-2026}},
  year = {2026},
  note = {Theorem 1.1.}
}

@article{KhotSafra2013,
  author = {Khot, Subhash and Safra, Muli},
  title = {A Two-Prover One-Round Game with Strong Soundness},
  journal = {Theory of Computing},
  volume = {9}, number = {28}, pages = {863--887}, year = {2013},
  doi = {10.4086/toc.2013.v009a028},
  note = {Preliminary version in FOCS 2011. \url{https://doi.org/10.4086/toc.2013.v009a028}}
}

@article{DinurGuruswami2015,
  author = {Dinur, Irit and Guruswami, Venkatesan},
  title = {{PCPs} via the low-degree long code and hardness for constrained hypergraph coloring},
  journal = {Israel Journal of Mathematics},
  volume = {209}, number = {2}, pages = {611--649}, year = {2015},
  doi = {10.1007/s11856-015-1231-3},
  note = {Preliminary version in FOCS 2013. Equation (1) and Fact 9 are cited in ECCC Report TR13-122: \url{https://eccc.weizmann.ac.il/report/2013/122/download/}}
}

@article{KhotSaket2017,
  author = {Khot, Subhash and Saket, Rishi},
  title = {Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with {$2^{(\log n)^{\Omega(1)}}$} Colors},
  journal = {SIAM Journal on Computing},
  volume = {46}, number = {1}, pages = {235--271}, year = {2017},
  doi = {10.1137/15100240X},
  note = {Preliminary version in FOCS 2014. Sections 2.1 and 7.2 are cited in ECCC Report TR14-051: \url{https://eccc.weizmann.ac.il/report/2014/051/download/}}
}

@article{Hastad2014NotTwo,
  author = {H{\aa}stad, Johan},
  title = {On the {NP}-Hardness of {Max-Not-2}},
  journal = {SIAM Journal on Computing},
  volume = {43}, number = {1}, pages = {179--193}, year = {2014},
  doi = {10.1137/120882718},
  note = {Preliminary version in APPROX 2012. \url{https://www.csc.kth.se/~johanh/sicompnottwo.pdf}}
}

@techreport{Golowich2023,
  author = {Golowich, Louis},
  title = {From {Grassmannian} to Simplicial High-Dimensional Expanders},
  institution = {Electronic Colloquium on Computational Complexity},
  type = {Report},
  number = {TR23-065},
  year = {2023},
  note = {\url{https://eccc.weizmann.ac.il/report/2023/065/}}
}