[1]   Michael Alekhnovich, Sanjeev Arora, and Iannis Tourlakis: Towards strong nonapproximability results in the Lovász–Schrijver hierarchy. Comput. Complexity, 20(4):615–648, 2011. Preliminary version in STOC’05. [doi:10.1007/s00037-011-0027-z]

[2]   Sanjeev Arora, Béla Bollobás, and László Lovász: Proving integrality gaps without knowing the linear program. In Proc. 43rd FOCS, pp. 313–322. IEEE Comp. Soc. Press, 2002. [doi:10.1109/SFCS.2002.1181954]

[3]   Sanjeev Arora, Béla Bollobás, László Lovász, and Iannis Tourlakis: Proving integrality gaps without knowing the linear program. Theory of Computing, 2(2):19–51, 2006. [doi:10.4086/toc.2006.v002a002]

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

[5]   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, arXiv:1501.00734]

[6]   Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani: SDP gaps from pairwise independence. Theory of Computing, 8(12):269–289, 2012. [doi:10.4086/toc.2012.v008a012]

[7]   Siu On Chan, James R. Lee, Prasad Raghavendra, and David Steurer: Approximate constraint satisfaction requires large LP relaxations. J. ACM, 63(4):34:1–34:22, 2016. Preliminary version in FOCS’13. [doi:10.1145/2811255, arXiv:1309.0563]

[8]   Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, and Serge Plotkin: Approximating a finite metric by a small number of tree metrics. In Proc. 39th FOCS, pp. 379–388. IEEE Comp. Soc. Press, 1998. [doi:10.1109/SFCS.1998.743488]

[9]   Moses Charikar, Konstantin Makarychev, and Yury Makarychev: Integrality gaps for Sherali–Adams relaxations. In Proc. 41st STOC, pp. 283–292. ACM Press, 2009. [doi:10.1145/1536414.1536455]

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

[11]   Moses Charikar, Konstantin Makarychev, and Yury Makarychev: Local global tradeoffs in metric embeddings. SIAM J. Comput., 39(6):2487–2512, 2010. Preliminary version in FOCS’07. [doi:10.1137/070712080]

[12]   Wenceslas Fernandez de la Vega and Claire Kenyon-Mathieu: Linear programming relaxations of maxcut. In Proc. 18th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’07), pp. 53–61. ACM Press, 2007. ACM DL.

[13]   Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald de Wolf: Exponential lower bounds for polytopes in combinatorial optimization. J. ACM, 62(2):17:1–17:23, 2015. Preliminary version in STOC’12. [doi:10.1145/2716307, arXiv:1111.0837]

[14]   Mrinalkanti Ghosh and Madhur Tulsiani: From weak to strong LP gaps for all CSPs. In Proc. 32nd Computational Complexity Conference (CCC’17), pp. 11:1–11:27. DROPS, 2017. [doi:10.4230/LIPIcs.CCC.2017.11, arXiv:1608.00497]

[15]   Sreyash Kenkre, Vinayaka Pandit, Manish Purohit, and Rishi Saket: On the approximability of digraph ordering. Algorithmica, 78(4):1182–1205, 2017. Preliminary version in ESA’15. [doi:10.1007/s00453-016-0227-7, arXiv:1507.00662]

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

[17]   Subhash Khot and Rishi Saket: SDP integrality gaps with local ℓ₁-embeddability. In Proc. 50th FOCS, pp. 565–574. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.37]

[18]   Subhash Khot and Rishi Saket: Approximating CSPs using LP relaxation. In Proc. 42nd Internat. Colloq. on Automata, Languages and Programming (ICALP’15), pp. 822–833. Springer, 2015. [doi:10.1007/978-3-662-47672-7_67]

[19]   Subhash 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]

[20]   Vladimir Kolmogorov, Johan Thapper, and Stanislav Živný: The power of linear programming for general-valued CSPs. SIAM J. Comput., 44(1):1–36, 2015. Preliminary versions in FOCS’12 and ICALP’13. [doi:10.1137/130945648, arXiv:1311.4219]

[21]   Pravesh K. Kothari, Raghu Meka, and Prasad Raghavendra: Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. In Proc. 49th STOC, pp. 590–603. ACM Press, 2017. [doi:10.1145/3055399.3055438, arXiv:1610.02704]

[22]   Pravesh K. Kothari, Ryuhei Mori, Ryan O’Donnell, and David Witmer: Sum of squares lower bounds for refuting any CSP. In Proc. 49th STOC, pp. 132–145. ACM Press, 2017. [doi:10.1145/3055399.3055485, arXiv:1701.04521]

[23]   Robert Krauthgamer, James R. Lee, Manor Mendel, and Assaf Naor: Measured descent: A new embedding method for finite metrics. Geom. Funct. Anal. GAFA, 15(4):839–858, 2005. Preliminary version in FOCS’04. [doi:10.1007/s00039-005-0527-6, arXiv:cs/0412008]

[24]   Euiwoong Lee: Hardness of graph pricing through generalized Max-Dicut. In Proc. 47th STOC, pp. 391–399. ACM Press, 2015. [doi:10.1145/2746539.2746549, arXiv:1405.0740]

[25]   László Lovász and Alexander Schrijver: Cones of matrices and set-functions and 0–1 optimization. SIAM J. Optim., 1(12):166–190, 1991. [doi:10.1137/0801013]

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

[27]   Prasad Raghavendra and David Steurer: Integrality gaps for strong SDP relaxations of Unique Games. In Proc. 50th FOCS, pp. 575–585. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.73]

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

[29]   Hanif D. Sherali and Warren P. Adams: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math., 3(3):411–430, 1990. [doi:10.1137/0403036]

[30]   Johan Håstad: On the efficient approximability of Constraint Satisfaction Problems. In Surveys in Combinatorics, volume 346, pp. 201–222. Cambridge University Press, 2007. [doi:10.1017/CBO9780511666209.008]

[31]   Johan Thapper and Stanislav Živný: The complexity of finite-valued CSPs. J. ACM, 63(4):37:1–37:33, 2016. Preliminary version in STOC’13. [doi:10.1145/2974019, arXiv:1210.2987]

[32]   Johan Thapper and Stanislav Živný: The power of Sherali–Adams relaxations for general-valued CSPs. SIAM J. Comput., 46(4):1241–1279, 2017. [doi:10.1137/16M1079245, arXiv:1606.02577]

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