[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. Preliminary version in STOC’93. [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. Preliminary version in FOCS’92. [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. Preliminary version in FOCS’92. [doi:10.1145/273865.273901]

[4]   Per Austrin, Subhash A. Khot, and Muli Safra: Inapproximability of vertex cover and independent set in bounded degree graphs. Theory of Computing, 7(3):27–43, 2011. [doi:10.4086/toc.2011.v007a003]

[5]   Per Austrin, Rajsekar Manokaran, and Cenny Wenner: On the NP-hardness of approximating ordering-constraint satisfaction problems. Theory of Computing, 11(10):257–283, 2015. [doi:10.4086/toc.2015.v011a010]

[6]   Per Austrin and Elchanan Mossel: Approximation resistant predicates from pairwise independence. Comput. Complexity, 18(2):249–271, 2009. [doi:10.1007/s00037-009-0272-6]

[7]   Nikhil Bansal, Anupam Gupta, and Guru Guruganesh: On the Lovász theta function for independent sets in sparse graphs. SIAM J. Comput., 47(3):1039–1055, 2018. Preliminary version in STOC’15. [doi:10.1137/15M1051002]

[8]   Nikhil Bansal and Subhash A. Khot: Inapproximability of hypergraph vertex cover and applications to scheduling problems. In Proc. 37th Internat. Colloq. on Automata, Languages, and Programming (ICALP’10), pp. 250–261. Springer, 2010. [doi:10.1007/978-3-642-14165-2_22]

[9]   Boaz Barak, Siu On Chan, and Pravesh K. Kothari: Sum of squares lower bounds from pairwise independence. In Proc. 47th STOC, pp. 97–106. ACM Press, 2015. [doi:10.1145/2746539.2746625]

[10]   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]

[11]   Amey Bhangale, Rajiv Gandhi, Mohammad Taghi Hajiaghayi, Rohit Khandekar, and Guy Kortsarz: Bi-covering: Covering edges with two small subsets of vertices. SIAM J. Discr. Math., 31(4):2626–2646, 2017. [doi:10.1137/16M1082421]

[12]   Amey Bhangale and Subhash A. Khot: UG-hardness to NP-hardness by losing half. In Proc. 34th Comput. Complexity Conf. (CCC’19), pp. 3:1–20. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.CCC.2019.3]

[13]   Siu On Chan: Approximation resistance from pairwise-independent subgroups. J. ACM, 63(3):27:1–32, 2016. [doi:10.1145/2873054]

[14]   Irit Dinur, Subhash A. Khot, Guy Kindler, Dor Minzer, and Muli Safra: On non-optimally expanding sets in Grassmann graphs. In Proc. 50th STOC, pp. 940–951. ACM Press, 2018. [doi:10.1145/3188745.3188806]

[15]   Irit Dinur, Subhash A. Khot, Guy Kindler, Dor Minzer, and Muli Safra: Towards a proof of the 2-to-1 games conjecture? In Proc. 50th STOC, pp. 376–389. ACM Press, 2018. [doi:10.1145/3188745.3188804]

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

[17]   Venkatesan Guruswami, Rajsekar Manokaran, and Prasad Raghavendra: Beating the random ordering is hard: Inapproximability of maximum acyclic subgraph. In Proc. 49th FOCS, pp. 573–582. IEEE Comp. Soc., 2008. [doi:10.1109/FOCS.2008.51]

[18]   Subhash A. 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]

[19]   Subhash A. Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319–357, 2007. [doi:10.1137/S0097539705447372]

[20]   Subhash A. 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]

[21]   Subhash A. Khot, Dor Minzer, and Muli Safra: Pseudorandom sets in Grassmann graph have near-perfect expansion. In Proc. 59th FOCS, pp. 592–601. IEEE Comp. Soc., 2018. [doi:10.1109/FOCS.2018.00062]

[22]   Subhash A. Khot and Assaf Naor: Approximate kernel clustering. Mathematika, 55(1–2):129–165, 2009. Preliminary version in FOCS’08. [doi:10.1112/S002557930000098X]

[23]   Subhash A. 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]

[24]   Subhash A. Khot, Madhur Tulsiani, and Pratik Worah: A characterization of strong approximation resistance. In Proc. 46th STOC, pp. 634–643. ACM Press, 2014. [doi:10.1145/2591796.2591817]

[25]   Subhash A. Khot and Nisheeth K. Vishnoi: The Unique Games Conjecture, integrality gap for cut problems and embeddability of negative-type metrics into ℓ₁. J. ACM, 62(1):8:1–23, 2015. [doi:10.1145/2629614]

[26]   Alantha Newman: The maximum acyclic subgraph problem and degree-3 graphs. In Proc. 4th Internat. Workshop on Approximation Algorithms for Combinat. Opt. Probl. (APPROX’01), pp. 147–158. Springer, 2001. [doi:10.1007/3-540-44666-4_18]

[27]   Prasad Raghavendra: Optimal algorithms and inapproximability results for every CSP? In Proc. 40th STOC, pp. 245–254. ACM Press, 2008. [doi:10.1145/1374376.1374414]

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