[1]   Sanjeev Arora, László Babai, Jacques Stern, and Elizabeth 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 FOCS’93. [doi:10.1006/jcss.1997.1472]

[2]   Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, and Muli Safra: On non-approximability for quadratic programs. In Proc. 46th FOCS, pp. 206–215. IEEE Comp. Soc. Press, 2005. See also at ECCC. [doi:10.1109/SFCS.2005.57]

[3]   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. See also at ECCC. [doi:10.1145/278298.278306]

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

[5]   Sanjeev Arora and Madhu Sudan: Improved low-degree testing and its applications. Combinatorica, 23(3):365–426, 2003. Preliminary version in STOC’97. [doi:10.1007/s00493-003-0025-0]

[6]   Mihir Bellare, Oded Goldreich, and Madhu Sudan: Free bits, PCPs, and nonapproximability—towards tight results. SIAM J. Comput., 27(3):804–915, 1998. Preliminary version in FOCS’95. See also at ECCC. [doi:10.1137/S0097539796302531]

[7]   Mihir Bellare, Shafi Goldwasser, Carsten Lund, and A. Russell: Efficient probabilistically checkable proofs and applications to approximations. In Proc. 25th STOC, pp. 294–304. ACM Press, 1993. See correction to abstract in STOC’94. [doi:10.1145/167088.167174]

[8]   Manuel Blum, Michael Luby, and Ronitt Rubinfeld: Self-testing/correcting with applications to numerical problems. J. Comput. System Sci., 47(3):549–595, 1993. Preliminary version in STOC’90. [doi:10.1016/0022-0000(93)90044-W]

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

[10]   Moses Charikar and Anthony Wirth: Maximizing quadratic programs: extending Grothendieck’s inequality. In Proc. 45th FOCS, pp. 54–60. IEEE Comp. Soc. Press, 2004. [doi:10.1109/FOCS.2004.39]

[11]   Anne Condon: The complexity of the max word problem and the power of one-way interactive proof systems. Comput. Complexity, 3(3):292–305, 1993. Preliminary version in STACS’91. [doi:10.1007/BF01271372]

[12]   Lars Engebretsen and Jonas Holmerin: More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP. Random Structures & Algorithms, 33(4):497–514, 2008. Preliminary version in STACS’05. [doi:10.1002/rsa.20226]

[13]   Uriel Feige: A threshold of lnn for approximating set cover. J. ACM, 45(4):634–652, 1998. Preliminary version in STOC’96. [doi:10.1145/285055.285059]

[14]   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. Preliminary version in FOCS’91. [doi:10.1145/226643.226652]

[15]   Timothy Gowers: A new proof of Szemerédi’s theorem for progressions of length four. Geometric and Functional Analysis, 8(3):529–551, 1998. [doi:10.1007/s000390050065]

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

[17]   Johan Håstad: Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. Preliminary version in STOC’97. [doi:10.1145/502090.502098]

[18]   Thomas Holenstein: Parallel repetition: Simplification and the no-signaling case. Theory of Computing, 5(8):141–172, 2009. Preliminary version in STOC’07. [doi:10.4086/toc.2009.v005a008]

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

[20]   Subhash 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. Preliminary version in FOCS’04. See also at ECCC. [doi:10.1137/S0097539705447372]

[21]   Subhash Khot and Ashok Kumar Ponnuswami: Better inapproximability results for maxclique, chromatic number and Min-3Lin-Deletion. In Proc. 33th Internat. Colloq. on Automata, Languages and Programming (ICALP’06), pp. 226–237. Springer, 2006. [doi:10.1007/11786986_21]

[22]   Subhash Khot and Muli Safra: A two prover one round game with strong soundness. In Proc. 52nd FOCS, pp. 648–657. IEEE Comp. Soc. Press, 2011. [doi:10.1109/FOCS.2011.62]

[23]   Alexandre Megretski: Relaxation of quadratic programs in operator theory and system analysis. In Proc. International Workshop on Operator Theory and Applications (IWOTA’00), pp. 365–392. Springer, 2000. [doi:10.1007/978-3-0348-8362-7_15]

[24]   Dana Moshkovitz: The projection games conjecture and the NP-hardness of lnn-approximating set-cover. In Proc. 15th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’12), pp. 276–287. Springer, 2012. See also at ECCC. [doi:10.1007/978-3-642-32512-0_24]

[25]   Dana Moshkovitz and Ran Raz: Two-query PCP with subconstant error. J. ACM, 57(5):29:1–29:29, 2010. Preliminary version in FOCS’08. See also at ECCC. [doi:10.1145/1754399.1754402]

[26]   Arkadi Nemirovski, Kees Roos, and Tamás Terlaky: On maximization of quadratic form over intersection of ellipsoids with common center. Mathematical Programming, 86(3):463–473, 1999. [doi:10.1007/s101070050100]

[27]   David Pollard: A user’s guide to measure theoretic probability. Cambridge Univ. Press, 2002. CUP.

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

[29]   Ran Raz: A parallel repetition theorem. SIAM J. Comput., 27(3):763–803, 1998. Preliminary version in STOC’95. [doi:10.1137/S0097539795280895]

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

[31]   Alex Samorodnitsky and Luca Trevisan: A PCP characterization of NP with optimal amortized query complexity. In Proc. 32nd STOC, pp. 191–199. ACM Press, 2000. [doi:10.1145/335305.335329]