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

[2]   Sarah R. Allen, Ryan O’Donnell, and David Witmer: How to refute a random CSP. In Proc. 56th FOCS, pp. 689–708. IEEE Comp. Soc., 2015. [doi:10.1109/FOCS.2015.48]

[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]   Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, and Santosh Vempala: Local versus global properties of metric spaces. SIAM J. Comput., 41(1):250–271, 2012. [doi:10.1137/090780304]

[5]   Francisco Barahona and Ali Ridha Mahjoub: On the cut polytope. Math. Programming, 36(2):157–173, 1986. [doi:10.1007/BF02592023]

[6]   Boaz Barak, Moritz Hardt, Thomas Holenstein, and David Steurer: Subsampling mathematical relaxations and average-case complexity. In Proc. 22nd Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’11), pp. 512–531. SIAM, 2011. [doi:10.1137/1.9781611973082.41]

[7]   Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh K. Kothari, Ankur Moitra, and Aaron Potechin: A nearly tight Sum-of-Squares lower bound for the Planted Clique problem. SIAM J. Comput., 48(2):687–735, 2019. Preliminary version in FOCS’16. [doi:10.1137/17M1138236]

[8]   Boaz Barak, Prasad Raghavendra, and David Steurer: Rounding semidefinite programming hierarchies via global correlation. In Proc. 52nd FOCS, pp. 472–481. IEEE Comp. Soc., 2011. [doi:10.1109/FOCS.2011.95]

[9]   Colin R. Blyth: Expected absolute error of the usual estimator of the binomial parameter. The American Statistician, 34(3):155–157, 1980. [doi:10.1080/00031305.1980.10483022]

[10]   Ravi B. Boppana: Eigenvalues and graph bisection: An average-case analysis. In Proc. 28th FOCS, pp. 280–285. IEEE Comp. Soc., 1987. [doi:10.1109/SFCS.1987.22]

[11]   Andrei Z. Broder, Alan M. Frieze, Stephen Suen, and Eli Upfal: Optimal construction of edge-disjoint paths in random graphs. SIAM J. Comput., 28(2):541–573, 1998. [doi:10.1137/S0097539795290805]

[12]   Siu On Chan, James R. Lee, Prasad Raghavendra, and David Steurer: Approximate constraint satisfaction requires large LP relaxations. J. ACM, 63(4):34:1–22, 2016. [doi:10.1145/2811255]

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

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

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

[16]   Nicholas Cook, Larry Goldstein, and Tobias Johnson: Size biased couplings and the spectral gap for random regular graphs. Ann. Probab., 46(1):72–125, 2018. [doi:10.1214/17-AOP1180]

[17]   Charles Delorme and Svatopluk Poljak: Laplacian eigenvalues and the maximum cut problem. Math. Programming, 62(1–3):557–574, 1993. ACM DL.

[18]   Michel Marie Deza and Monique Laurent: Geometry of Cuts and Metrics. Volume 15 of Algorithms and Combinatorics. Springer, 1997. [doi:10.1007/978-3-642-04295-9]

[19]   William E. Donath and Alan J. Hoffman: Lower bounds for the partitioning of graphs. IBM J. Res. Dev., 17(5):420–425, 1973. Included in “Selected Papers of Alan J. Hoffman: With Commentary” (World Scientific, 2003, pp. 437–442). [doi:10.1147/rd.175.0420]

[20]   Uriel Feige and Robert Krauthgamer: The probable value of the Lovász–Schrijver relaxations for maximum independent set. SIAM J. Comput., 32(2):345–370, 2003. [doi:10.1137/S009753970240118X]

[21]   Uriel Feige and Michael Langberg: The RPR² rounding technique for semidefinite programs. J. Algorithms, 60(1):1–23, 2006. Preliminary version in ICALP’01. [doi:10.1016/j.jalgor.2004.11.003]

[22]   Uriel Feige and Eran Ofek: Spectral techniques applied to sparse random graphs. Random Struct. Algor., 27(2):251–275, 2005. [doi:10.1002/rsa.20089]

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

[24]   Miroslav Fiedler: Algebraic connectivity of graphs. Czechoslovak Math. J., 23(2):298–305, 1973. [doi:10.21136/CMJ.1973.101168]

[25]   Joel Friedman, Andreas Goerdt, and Michael Krivelevich: Recognizing more unsatisfiable random k-SAT instances efficiently. SIAM J. Comput., 35(2):408–430, 2005. [doi:10.1137/S009753970444096X]

[26]   Joel Friedman, Jeff Kahn, and Endre Szemerédi: On the second eigenvalue of random regular graphs. In Proc. 21st STOC, pp. 587–598. ACM Press, 1989. [doi:10.1145/73007.73063]

[27]   Alan Frieze and Ravi Kannan: The regularity lemma and approximation schemes for dense problems. In Proc. 37th FOCS, pp. 12–20. IEEE Comp. Soc., 1996. [doi:10.1109/SFCS.1996.548459]

[28]   Michel X. Goemans and David P. Williamson: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115–1145, 1995. [doi:10.1145/227683.227684]

[29]   Andreas Goerdt and Michael Krivelevich: Efficient recognition of random unsatisfiable k-SAT instances by spectral methods. In Proc. 18th Symp. Theoret. Aspects of Comp. Sci. (STACS’01), pp. 294–304. Springer, 2001. [doi:10.1007/3-540-44693-1_26]

[30]   Dima Grigoriev: Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. Theoret. Comput. Sci., 259(1–2):613–622, 2001. [doi:10.1016/S0304-3975(00)00157-2]

[31]   Johan Håstad: An NP-complete problem – some aspects of its solution and some possible applications. Technical Report 16, Inst. Mittag-Leffler, 1984.

[32]   Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer: The power of sum-of-squares for detecting hidden structures. In Proc. 58th FOCS, pp. 720–731. IEEE Comp. Soc., 2017. [doi:10.1109/FOCS.2017.72]

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

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

[35]   David A. Levin and Yuval Peres: Counting walks and graph homomorphisms via Markov chains and importance sampling. Amer. Math. Monthly, 124(7):637–641, 2017. [doi:10.4169/amer.math.monthly.124.7.637]

[36]   Bojan Mohar and Svatopluk Poljak: Eigenvalues in combinatorial optimization. In Combinatorial and Graph-Theoretical Problems in Linear Algebra, pp. 107–151. Springer, 1993. [doi:10.1007/978-1-4613-8354-3_5]

[37]   Ryan O’Donnell and Tselil Schramm: Sherali–Adams strikes back. In Proc. 34th Comput. Complexity Conf. (CCC’19), pp. 8:1–30. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.CCC.2019.8]

[38]   Svatopluk Poljak: Polyhedral and eigenvalue approximations of the max-cut problem. In Sets, Graphs and Numbers (Budapest, 1991), volume 60 of Colloq. Math. Soc. János Bolyai, pp. 569–581. North-Holland, 1992. LINK.

[39]   Svatopluk Poljak and Zsolt Tuza: The expected relative error of the polyhedral approximation of the max-cut problem. Oper. Res. Lett., 16(4):191–198, 1994. [doi:10.1016/0167-6377(94)90068-X]

[40]   Prasad Raghavendra, Satish Rao, and Tselil Schramm: Strongly refuting random CSPs below the spectral threshold. In Proc. 49th STOC, pp. 121–131. ACM Press, 2017. [doi:10.1145/3055399.3055417]

[41]   Prasad Raghavendra, Tselil Schramm, and David Steurer: High-dimensional estimation via sum-of-squares proofs. In Proc. Internat. Congress of Mathematicians (ICM’18), volume 4, pp. 3389–3424. World Scientific, 2019. [doi:10.1142/9789813272880_0186, arXiv:1807.11419]

[42]   Prasad Raghavendra and Ning Tan: Approximating CSPs with global cardinality constraints using SDP hierarchies. In Proc. 23rd Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’12), pp. 373–387. SIAM, 2012. [doi:10.1137/1.9781611973099.33, arXiv:1110.1064]

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

[44]   Grant Schoenebeck, Luca Trevisan, and Madhur Tulsiani: Tight integrality gaps for Lovász–Schrijver LP relaxations of vertex cover and max cut. In Proc. 39th STOC, pp. 302–310. ACM Press, 2007. [doi:10.1145/1250790.1250836]

[45]   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. Discr. Math., 3(3):411–430, 1990. [doi:10.1137/0403036]

[46]   Konstantin Tikhomirov and Pierre Youssef: The spectral gap of dense random regular graphs. Ann. Probab., 47(1):362–419, 2019. [doi:10.1214/18-AOP1263, arXiv:1610.01765]

[47]   Luca Trevisan: Max cut and the smallest eigenvalue. SIAM J. Comput., 41(6):1769–1786, 2012. Preliminary version in STOC’09. [doi:10.1137/090773714]

[48]   Joel A. Tropp: An Introduction to Matrix Concentration Inequalities. Foundations and Trends®; in Machine Learning, 8(1–2):1–230, 2015. [doi:10.1561/2200000048, arXiv:1501.01571]

[49]   Uri Zwick: Outward rotations: A tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems. In Proc. 31st STOC, pp. 679–687. ACM Press, 1999. [doi:10.1145/301250.301431]