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

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

[3]   Per Austrin and Johan Håstad: On the usefulness of predicates. ACM Trans. Computation Theory, 5(1):1, 2013. Preliminary version in CCC’12. [doi:10.1145/2462896.2462897]

[4]   Per Austrin and Elchanan Mossel: Approximation resistant predicates from pairwise independence. Comput. Complexity, 18(2):249–271, 2009. Preliminary version in CCC’08. See also at ECCC. [doi:10.1007/s00037-009-0272-6]

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

[6]   Moses Charikar, Konstantin Makarychev, and Yury Makarychev: Near-optimal algorithms for maximum constraint satisfaction problems. ACM Trans. Algorithms, 5(3):32:1–32:14, 2009. Preliminary version in SODA’07. [doi:10.1145/1541885.1541893]

[7]   Irit Dinur, Venkatesan Guruswami, Subhash Khot, and Oded Regev: A new multilayered PCP and the hardness of hypergraph vertex cover. SIAM J. Comput., 34(5):1129–1146, 2005. Preliminary version in STOC’03. [doi:10.1137/S0097539704443057]

[8]   Bradley Efron and Charles Stein: The jackknife estimate of variance. Ann. Stat., 9(3):586–596, 1981. [doi:10.1214/aos/1176345462]

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

[10]   Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, and Yi Wu: Agnostic learning of monomials by halfspaces is hard. SIAM J. Comput., 41(6):1558–1590, 2012. Preliminary version in FOCS’09. [doi:10.1137/120865094]

[11]   Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, and Yi Wu: Bypassing UGC from some optimal geometric inapproximability results. In Proc. 23rd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’12), pp. 699–717. ACM Press, 2012. See also at ECCC. [ACM:2095174]

[12]   Gustav Hast: Beating a random assignment. In Proc. 9th Internat. Workshop on Randomization and Computation (RANDOM’05), volume 3624 of LNCS, pp. 134–145. Springer, 2005. [doi:10.1007/11538462_12]

[13]   Gustav Hast: Beating a Random Assignment: Approximating Constraint Satisfaction Problems. Ph. D. thesis, KTH Royal Institute of Technology, 2005. DiVA.

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

[15]   Johan Håstad: On the NP-hardness of Max-Not-2. SIAM J. Comput., 43(1):179–193, 2014. Preliminary version in APPROX’12. [doi:10.1137/120882718]

[16]   Johan Håstad and Subhash Khot: Query efficient PCPs with perfect completeness. Theory of Computing, 1(7):119–148, 2005. Preliminary version in FOCS’01. [doi:10.4086/toc.2005.v001a007]

[17]   Sangxia Huang: Approximation resistance on satisfiable instances for predicates strictly dominating parity. Electron. Colloq. on Comput. Complexity (ECCC), 19:40, 2012. ECCC.

[18]   Sangxia Huang: Approximation resistance on satisfiable instances for predicates with few accepting inputs. In Proc. 45th STOC, pp. 457–466. ACM Press, 2013. [doi:10.1145/2488608.2488666]

[19]   Subhash Khot: Hardness results for coloring 3-colorable 3-uniform hypergraphs. In Proc. 43rd FOCS, pp. 23–32. IEEE Comp. Soc. Press, 2002. [doi:10.1109/SFCS.2002.1181879]

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

[21]   Subhash Khot and Dana Moshkovitz: NP-hardness of approximately solving linear equations over reals. SIAM J. Comput., 42(3):752–791, 2013. Preliminary version in STOC’11. See also at ECCC. [doi:10.1137/110846415]

[22]   Elchanan Mossel: Gaussian bounds for noise correlation of functions and tight analysis of long codes. In Proc. 49th FOCS, pp. 156–165. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.44]

[23]   Elchanan Mossel: Gaussian bounds for noise correlation of functions. Geom. Funct. Anal., 19(6):1713–1756, 2010. Preliminary version in FOCS’08. [doi:10.1007/s00039-010-0047-x]

[24]   Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz: Noise stability of functions with low influences: invariance and optimality. Ann. of Math., 171(1):295–341, 2010. Preliminary version in FOCS’05. [doi:10.4007/annals.2010.171.295]

[25]   Ryan O’Donnell and John Wright: A new point of NP-hardness for unique games. In Proc. 44th STOC, pp. 289–306. ACM Press, 2012. [doi:10.1145/2213977.2214005]

[26]   Ryan O’Donnell and Yi Wu: Conditional hardness for satisfiable 3-CSPs. In Proc. 41st STOC, pp. 493–502. ACM Press, 2009. [doi:10.1145/1536414.1536482]

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

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

[29]   Alex Samorodnitsky and Luca Trevisan: Gowers uniformity, influence of variables, and PCPs. SIAM J. Comput., 39(1):323–360, 2009. Preliminary version in STOC’06. See also at ECCC. [doi:10.1137/070681612]

[30]   Linqing Tang: Conditional hardness of approximating satisfiable Max 3CSP-q. In Internat. Symp. Algorithms and Computation (ISAAC’09), pp. 923–932. Springer, 2009. [doi:10.1007/978-3-642-10631-6_93]

[31]   Luca Trevisan: Approximating satisfiable satisfiability problems. Algorithmica, 28(1):145–172, 2000. Preliminary version in ESA’97. [doi:10.1007/s004530010035]

[32]   Cenny Wenner: Circumventing d-to-1 for approximation resistance of satisfiable predicates strictly containing parity of width at least four. Theory of Computing, 9(23):703–757, 2013. Conference version in APPROX’12. [doi:10.4086/toc.2013.v009a023]

[33]   Uri Zwick: Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. In Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’98), pp. 201–210. ACM Press, 1998. [ACM:314701]