[1]   Dorit Aharonov and Oded Regev: Lattice problems in NP ∩ coNP. J. ACM, 52(5):749–765, 2005. Preliminary version in FOCS’04. [doi:10.1145/1089023.1089025]

[2]   Noga Alon, Dana Moshkovitz, and Shmuel Safra: Algorithmic construction of sets for k-restrictions. ACM Trans. Algorithms, 2(2):153–177, 2006. [doi:10.1145/1150334.1150336]

[3]   Sanjeev Arora, László Babai, Jacques Stern, and Elizabeth 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]

[4]   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 versions in FOCS’92 and ECCC. [doi:10.1145/278298.278306]

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

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

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

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

[9]   Moses Charikar, MohammadTaghi Hajiaghayi, and Howard J. Karloff: Improved approximation algorithms for label cover problems. Algorithmica, 61(1):190–206, 2011. Preliminary version in ESA’09. [doi:10.1007/s00453-010-9464-3]

[10]   Marek Cygan, Łukasz Kowalik, and Mateusz Wykurz: Exponential-time approximation of weighted set cover. Inform. Process. Lett., 109(16):957–961, 2009. [doi:10.1016/j.ipl.2009.05.003]

[11]   Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, and Shmuel Safra: PCP characterizations of NP: Toward a polynomially-small error-probability. Comput. Complexity, 20(3):413–504, 2011. Preliminary versions in STOC’99 and ECCC. [doi:10.1007/s00037-011-0014-4]

[12]   Irit Dinur, Guy Kindler, Ran Raz, and Shmuel Safra: Approximating CVP to within almost-polynomial factors is NP-hard. Combinatorica, 23(2):205–243, 2003. Preliminary versions in ECCC and FOCS’98. [doi:10.1007/s00493-003-0019-y]

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

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

[15]   Johan Håstad: On bounded occurrence constraint satisfaction. Inform. Process. Lett., 74(1-2):1–6, 2000. [doi:10.1016/S0020-0190(00)00032-6]

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

[17]   Ishay Haviv and Oded Regev: Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Theory of Computing, 8(23):513–531, 2012. Preliminary version in STOC’07. [doi:10.4086/toc.2012.v008a023]

[18]   Russell Impagliazzo and Ramamohan Paturi: On the complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367–375, 2001. Preliminary version in CCC’99. [doi:10.1006/jcss.2000.1727]

[19]   David S. Johnson: Approximation algorithms for combinatorial problems. J. Comput. System Sci., 9(3):256–278, 1974. [doi:10.1016/S0022-0000(74)80044-9]

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

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

[22]   Subhash Khot: Hardness of approximating the shortest vector problem in lattices. J. ACM, 52(5):789–808, 2005. Preliminary version in FOCS’04. [doi:10.1145/1089023.1089027]

[23]   Subhash Khot: Inapproximability results for computational problems on lattices. In The LLL Algorithm, pp. 453–473. Springer, 2010. [doi:10.1007/978-3-642-02295-1_14]

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

[25]   László Lovász: On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13(4):383–390, 1975. [doi:10.1016/0012-365X(75)90058-8]

[26]   Carsten Lund and Mihalis Yannakakis: On the hardness of approximating minimization problems. J. ACM, 41(5):960–981, 1994. Preliminary version in STOC’93. [doi:10.1145/185675.306789]

[27]   Pasin Manurangsi and Dana Moshkovitz: Improved approximation algorithms for projection games (Extended abstract). In ESA, pp. 683–694, 2013. Update in CoRR. [doi:10.1007/978-3-642-40450-4_58]

[28]   Daniele Micciancio and Shafi Goldwasser: Complexity of Lattice Problems: A cryptographic perspective. Volume 671 of Kluwer Ser. in Engin. and Comput. Sci. Kluwer, 2002.

[29]   Daniele Micciancio and Oded Regev: Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput., 37(1):267–302, 2007. Preliminary version in FOCS’04. [doi:10.1137/S0097539705447360]

[30]   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, 2012. Preliminary version in ECCC. [doi:10.1007/978-3-642-32512-0_24]

[31]   Dana Moshkovitz and Ran Raz: Sub-constant error low degree test of almost-linear size. SIAM J. Comput., 38(1):140–180, 2008. Preliminary version in STOC’06. [doi:10.1137/060656838]

[32]   Dana Moshkovitz and Ran Raz: Two-query PCP with sub-constant error. J. ACM, 57(5/29), 2010. Preliminary version in FOCS’08. [doi:10.1145/1754399.1754402]

[33]   Moni Naor, Leonard J. Schulman, and Aravind Srinivasan: Splitters and near-optimal derandomization. In Proc. 36th FOCS, pp. 182–191. IEEE Comp. Soc. Press, 1995. [doi:10.1109/SFCS.1995.492475]

[34]   David Peleg: Approximation algorithms for the Label-Cover_MAX and Red-Blue Set Cover problems. J. Discrete Algorithms, 5(1):55–64, 2007. Preliminary version in SWAT’00. [doi:10.1016/j.jda.2006.03.008]

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

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

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

[38]   Oded Regev: On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6/34):1–40, 2009. Preliminary version in STOC’05. [doi:10.1145/1568318.1568324]

[39]   Oded Regev: On the complexity of lattice problems with polynomial approximation factors. In The LLL Algorithm, pp. 475–496. Springer, 2010. [doi:10.1007/978-3-642-02295-1_15]

[40]   Petr Slavík: A tight analysis of the greedy algorithm for set cover. J. Algorithms, 25(2):237–254, 1997. Preliminary version in STOC’96. [doi:10.1006/jagm.1997.0887]

[41]   Aravind Srinivasan: Improved approximations guarantees for packing and covering integer programs. SIAM J. Comput., 29(2):648–670, 1999. [doi:10.1137/S0097539796314240]

[42]   Sherman K. Stein: Two combinatorial covering theorems. J. Combin. Theory Ser. A, 16(3):391–397, 1974. [doi:10.1016/0097-3165(74)90062-4]