[1]   Sanjeev Arora, László Babai, Jacques Stern, and Z. Sweedyk: The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. System Sci., 54(2):317–331, 1997. [doi:10.1006/jcss.1997.1472]

[2]   Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy: Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555, 1998. [doi:10.1145/278298.278306]

[3]   Sanjeev Arora and Shmuel Safra: Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70–122, 1998. [doi:10.1145/273865.273901]

[4]   Boaz Barak, Pravesh K. Kothari, and David Steurer: Small-set expansion in shortcode graph and the 2-to-2 conjecture. In Proc. 10th Innovations in Theoret. Comp. Sci. Conf. (ITCS’19), pp. 9:1–12. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.ITCS.2019.9]

[5]   Mihir Bellare, Oded Goldreich, and Madhu Sudan: Free bits, PCPs, and nonapproximability – Towards tight results. SIAM J. Comput., 27(3):804–915, 1998. [doi:10.1137/S0097539796302531]

[6]   Volodia M. Blinovsky: Bounds for codes in the case of list decoding of finite volume. Problems of Information Transmission, 22(1):7–19, 1986. Russian original accessible at Mathnet.ru.

[7]   Andries E. Brouwer, Arjeh M. Cohen, and Arnold Neumaier: Distance-Regular Graphs. Springer, 2012. Google books. [doi:10.1007/978-3-642-74341-2]

[8]   Siu On Chan: Approximation resistance from pairwise independent subgroups. In Proc. 45th STOC, pp. 447–456. ACM Press, 2013. [doi:10.1145/2488608.2488665]

[9]   Ameera Chowdhury and Balázs Patkós: Shadows and intersections in vector spaces. J. Combin. Theory–A, 117(8):1095–1106, 2010. [doi:10.1016/j.jcta.2009.10.010]

[10]   Irit Dinur: The PCP theorem by gap amplification. J. ACM, 54(3):1–44, 2007. [doi:10.1145/1236457.1236459]

[11]   Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra: On non-optimally expanding sets in Grassmann graphs. Israel J. Math., 243(1):377–420, 2021. [doi:10.1007/s11856-021-2164-7]

[12]   Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra: Towards a proof of the 2-to-1 Games Conjecture? Theory of Computing, 21(11):1–50, 2025. Preliminary version in STOC’18. [doi:10.4086/toc.2025.v021a011]

[13]   Irit Dinur, Elchanan Mossel, and Oded Regev: Conditional hardness for approximate coloring. SIAM J. Comput., 39(3):843–873, 2009. [doi:10.1137/07068062X]

[14]   Irit Dinur and Samuel Safra: On the hardness of approximating minimum vertex cover. Ann. Math., 162(1):439–485, 2005. Accessible at JSTOR.

[15]   Irit Dinur and David Steurer: Analytical approach to parallel repetition. In Proc. 46th STOC, pp. 624–633. ACM Press, 2014. [doi:10.1145/2591796.2591884]

[16]   Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy: Interactive proofs and the hardness of approximating cliques. J. ACM, 43(2):268–292, 1996. [doi:10.1145/226643.226652]

[17]   Ehud Friedgut: Boolean functions with low average sensitivity depend on few coordinates. Combinatorica, 18(1):27–35, 1998. [doi:10.1007/PL00009809]

[18]   Dima Grigoriev: Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. Theoret. Comput. Sci., 259(1–2):613–622, 2001. [doi:10.1016/S0304-3975(00)00157-2]

[19]   Venkatesan Guruswami, Johan Håstad, and Madhu Sudan: Hardness of approximate hypergraph coloring. SIAM J. Comput., 31(6):1663–1686, 2002. [doi:10.1137/S0097539700377165]

[20]   Eran Halperin: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput., 31(5):1608–1623, 2002. [doi:10.1137/S0097539700381097]

[21]   Johan Håstad: Clique is hard to approximate within n^1-ϵ. Acta Math., 182:105–142, 1999. Preliminary version in FOCS’96. [doi:10.1007/BF02392825]

[22]   Johan Håstad: Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. [doi:10.1145/502090.502098]

[23]   Thomas Holenstein: Parallel repetition: Simplifications and the no-signaling case. Theory of Computing, 5(8):141–172, 2009. [doi:10.4086/toc.2009.v005a008]

[24]   George Karakostas: A better approximation ratio for the vertex cover problem. ACM Trans. Algorithms, 5(4/41):1–8, 2009. [doi:10.1145/1597036.1597045]

[25]   Subhash Khot: Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring. In Proc. 42nd FOCS, pp. 600–609. IEEE Comp. Soc., 2001. [doi:10.1109/SFCS.2001.959936]

[26]   Subhash Khot: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp. 767–775. ACM Press, 2002. [doi:10.1145/509907.510017]

[27]   Subhash Khot: Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput., 36(4):1025–1071, 2006. [doi:10.1137/S0097539705447037]

[28]   Subhash Khot: Inapproximability of NP-complete problems, discrete Fourier analysis, and geometry. In Proc. International Congress of Mathematicians, pp. 2676–2697. World Scientific, 2010. Accessible at author’s website. [doi:10.1142/9789814324359_0163]

[29]   Subhash Khot: On the unique games conjecture. In Proc. 25th IEEE Conf. on Comput. Complexity (CCC’10), pp. 99–121. IEEE Comp. Soc., 2010. [doi:10.1109/CCC.2010.19]

[30]   Subhash Khot, Dor Minzer, Dana Moshkovitz, and Muli Safra: Small set expansion in the Johnson graph. Theory of Computing, 21(2):1–43, 2025. [doi:10.4086/toc.2025.v021a002, ECCC:TR18-078]

[31]   Subhash Khot, Dor Minzer, and Muli Safra: On independent sets, 2-to-2 games, and Grassmann graphs. In Proc. 49th STOC, pp. 576–589. ACM Press, 2017. [doi:10.1145/3055399.3055432]

[32]   Subhash Khot, Dor Minzer, and Muli Safra: Pseudorandom sets in Grassmann graph have near-perfect expansion. Ann. Math., 198(1):1–92, 2023. [doi:10.4007/annals.2023.198.1.1]

[33]   Subhash Khot and Oded Regev: Vertex cover might be hard to approximate to within 2-ϵ. J. Comput. System Sci., 74(3):335–349, 2008. [doi:10.1016/j.jcss.2007.06.019]

[34]   Subhash Khot and Muli Safra: A two-prover one-round game with strong soundness. Theory of Computing, 9(28):863–887, 2013. [doi:10.4086/toc.2013.v009a028]

[35]   Grigorii Margulis: Probabilistic characteristics of graphs with large connectivity. Problemy Peredachi Informatsii, 10(2):101–108, 1974. Russian original accessible at Mathnet.ru.

[36]   Anup Rao: Parallel repetition in projection games and a concentration bound. SIAM J. Comput., 40(6):1871–1891, 2011. [doi:10.1137/080734042]

[37]   Ran Raz: A parallel repetition theorem. SIAM J. Comput., 27(3):763–803, 1998. [doi:10.1137/S0097539795280895]

[38]   Ran Raz and Shmuel Safra: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proc. 29th STOC, pp. 475–484. ACM Press, 1997. [doi:10.1145/258533.258641]

[39]   Ronitt Rubinfeld and Madhu Sudan: Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252–271, 1996. [doi:10.1137/S0097539793255151]

[40]   Lucio Russo: An approximate zero-one law. Z. Wahrscheinlichkeitstheorie und verwandte Gebiete, 61(1):129–139, 1982. [doi:10.1007/BF00537230]

[41]   Grant Schoenebeck: Linear level Lasserre lower bounds for certain k-CSPs. In Proc. 49th FOCS, pp. 593–602. IEEE Comp. Soc., 2008. [doi:10.1109/FOCS.2008.74]

[42]   Luca Trevisan: On Khot’s unique games conjecture. Bull. AMS, 49(1):91–111, 2012. AMS link.

[43]   Madhur Tulsiani: CSP gaps and reductions in the Lasserre hierarchy. In Proc. 41st STOC, pp. 303–312. ACM Press, 2009. [doi:10.1145/1536414.1536457]