SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization

References

• [1] Arora S, Rao S, Vazirani UV (2009) Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2):5:1–5:37.Crossref, Google Scholar
• [2] Atserias A, Fijalkow J (2023) Definable ellipsoid method, sums-of-squares proofs, and the graph isomorphism problem. SIAM J. Comput. 52(5):1193–1229.Crossref, Google Scholar
• [3] Atserias A, Maneva E (2012) Sherali-Adams relaxations and indistinguishability in counting logics. Proc. 3rd Innovations in Theoret. Comput. Sci. Conf. (Association for Computing Machinery, New York), 367–379.Google Scholar
• [4] Babai L (2016) Graph isomorphism in quasipolynomial time. Proc. 48th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 684–697.Google Scholar
• [5] Baldi L, Slot L (2024) Degree bounds for Putinar’s positivstellensatz on the hypercube. SIAM J. Appl. Algebra Geometry 8(1):1–25.Crossref, Google Scholar
• [6] Barak B, Moitra A (2016) Noisy tensor completion via the sum-of-squares hierarchy. COLT 2016 (Association for Computational Learning, Mountain View, CA), 417–445.Google Scholar
• [7] Barak B, Steurer D (2016) Proofs, beliefs, and algorithms through the lens of sum-of-squares. Accessed September 22, 2016, https://www.sumofsquares.org.Google Scholar
• [8] Barak B, Kelner JA, Steurer D (2015) Dictionary learning and tensor decomposition via the sum-of-squares method. STOC’15 Proc. 47th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 143–151.Google Scholar
• [9] Barak B, Raghavendra P, Steurer D (2011) Rounding semidefinite programming hierarchies via global correlation. FOCS’11 Proc. 2011 IEEE 52nd Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 472–481.Google Scholar
• [10] Barak B, Hopkins SB, Kelner JA, Kothari P, Moitra A, Potechin A (2016) A nearly tight sum-of-squares lower bound for the planted clique problem. FOCS 2016 IEEE 57th Annual Symposium Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 428–437.Google Scholar
• [11] Bhaskara A, Charikar M, Vijayaraghavan A, Guruswami V, Zhou Y (2012) Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph. SODA’12 Proc. 23rd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 388–405.Google Scholar
• [12] Bienstock D, Zuckerberg M (2002) Subset algebra lift operators for 0-1 integer programming (extended version). SIAM J. Optim. 1(15):63–95.Google Scholar
• [13] Blekherman G, Gouveia J, Pfeiffer J (2016) Sums of squares on the hypercube. Math. Zeitschrift 284(1):41–54.Crossref, Google Scholar
• [14] Blekherman G, Parrilo PA, Thomas RR, eds. (2012) Semidefinite Optimization and Convex Algebraic Geometry, MOS-SIAM Series on Optimization (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [15] Chernof H (1952) A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statist. 23(4):493–507.Crossref, Google Scholar
• [16] Cheung KKH (2007) Computation of the Lasserre ranks of some polytopes. Math. Oper. Res. 32(1):88–94.Link, Google Scholar
• [17] Cook W, Dash S (2001) On the matrix-cut rank of polyhedra. Math. Oper. Res. 26(1):19–30.Link, Google Scholar
• [18] Cornuéjols G, Li Y (2001) On the rank of mixed 0, 1 polyhedra. Aardal K, Gerards B, eds. Integer Programming Combin. Optim. IPCO 2001, Lecture Notes in Computer Science, vol. 2081 (Springer, Berlin, Heidelberg), 71–77.Google Scholar
• [19] Delorme C, Poljak S (1993) Laplacian eigenvalues and the maximum cut problem. Math. Programming 62:557–574.Crossref, Google Scholar
• [20] d’Orsi T, Nasser R, Novikov G, Steurer D (2023) Higher degree sum-of-squares relaxations robust against oblivious outliers. Bansal N, Nagarajan V, eds. Proc. 2023 ACM-SIAM Sympos. Discrete Algorithms. SODA 2023 (Society for Industrial and Applied Mathematics, Philadelphia), 3513–3550.Google Scholar
• [21] Fawzi H, Saunderson J, Parrilo PA (2015) Sparse sum-of-squares certificates on finite abelian groups. 54th IEEE Conf. Decision Control. CDC 2015 (IEEE, Piscataway, NJ), 5909–5914.Google Scholar
• [22] Garey M, Johnson D (1978) “Strong” NP-completeness results: Motivation, examples, and implications. J. ACM 25(3):499–508.Crossref, Google Scholar
• [23] Ghosh M, Jeronimo FG, Jones C, Potechin A, Rajendran G (2020) Sum-of-squares lower bounds for Sherrington-Kirkpatrick via planted affine planes. 61st IEEE Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE Computer Society, Washington, DC), 954–965.Google Scholar
• [24] Goemans MX, Tunçel L (2001) When does the positive semidefiniteness constraint help in lifting procedures? Math. Oper. Res. 26(4):796–815.Link, Google Scholar
• [25] Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6):1115–1145.Crossref, Google Scholar
• [26] Grigoriev D (2001) Complexity of positivstellensatz proofs for the knapsack. Comput. Complexity 10(2):139–154.Crossref, Google Scholar
• [27] Grigoriev D (2001) Linear lower bound on degrees of positivstellensatz calculus proofs for the parity. Theoretical Comput. Sci. 259(1–2):613–622.Crossref, Google Scholar
• [28] Grigoriev D, Vorobjov N (2001) Complexity of null-and positivstellensatz proofs. Ann. Pure App. Logic 113(1–3):153–160.Crossref, Google Scholar
• [29] Grigoriev D, Hirsch EA, Pasechnik DV (2002) Complexity of semi-algebraic proofs. Alt H, Ferreira A, eds. STACS 2002, Lecture Notes in Computer Science, vol. 2285 (Springer, Berlin, Heidelberg), 419–430.Google Scholar
• [30] Guruswami V, Sinop AK (2011) Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with PSD objectives. IEEE 52nd Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE Computer Society, Washington, DC), 482–491.Google Scholar
• [31] Hopkins SB, Li J (2018) Mixture models, robustness, and sum of squares proofs. Proc. 50th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 1021–1034.Google Scholar
• [32] Hopkins SB, Kamath G, Majid M (2022) Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism. STOC 2022 Proc. 54th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 1406–1417.Google Scholar
• [33] Hopkins SB, Schramm T, Shi J, Steurer D (2016) Fast spectral algorithms from sum-of-squares proofs: Tensor decomposition and planted sparse vectors. STOC’16 Proc. 48th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 178–191.Google Scholar
• [34] Josz C, Henrion D (2016) Strong duality in Lasserre’s hierarchy for polynomial optimization. Optim. Lett. 10(1):3–10.Crossref, Google Scholar
• [35] Kothari P, Manurangsi P, Velingker A (2022) Private robust estimation by stabilizing convex relaxations. Loh P, Raginsky M, eds. Conf. Learning Theory, vol. 178 (PMLR, New York), 723–777.Google Scholar
• [36] Kothari P, Steinhardt J, Steurer D (2018) Robust moment estimation and improved clustering via sum of squares. STOC 2018 Proc. 50th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 1035–1046.Google Scholar
• [37] Kothari PK, Mori R, O’Donnell R, Witmer D (2017) Sum of squares lower bounds for refuting any CSP. STOC 2017 Proc. 49th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 132–145.Google Scholar
• [38] Kunisky D, Bandeira AS (2019) A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian. Preprint, submitted July 26, http://arxiv.org/abs/1907.11686.Google Scholar
• [39] Kurpisz A (2019) Sum-of-squares bounds via Boolean function analysis. Internat. Colloquium Automata Languages Programming (ICALP) (European Association for Theoretical Computer Science), 79:1–79:15.Google Scholar
• [40] Kurpisz A, Leppänen S, Mastrolilli M (2016) Tight sum-of-squares lower bounds for binary polynomial optimization problems. 43rd Internat. Colloquium Automata Languages Programming (ICALP) (European Association for Theoretical Computer Science), 78:1–78:14.Google Scholar
• [41] Kurpisz A, Leppänen S, Mastrolilli M (2017) On the hardest problem formulations for the 0/1 Lasserre hierarchy. Math. Oper. Res. 42(1):135–143.Link, Google Scholar
• [42] Kurpisz A, Leppänen S, Mastrolilli M (2017) An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem. Math. Programming 166(1–2):1–17.Crossref, Google Scholar
• [43] Kurpisz A, Leppänen S, Mastrolilli M (2020) Sum-of-squares hierarchy lower bounds for symmetric formulations. Math. Programming 182(1):369–397.Crossref, Google Scholar
• [44] Kurpisz A, Potechin A, Wirth ES (2021) Sos certification for symmetric quadratic functions and its connection to constrained Boolean hypercube optimization. 48th Internat. Colloquium Automata Languages Programming (ICALP 2021) (Schloss-Dagstuhl-Leibniz Zentrum für Informatik, Wadern, Germany).Google Scholar
• [45] Kurpisz A, Wirth E (2023) Sum of squares bounds for the empty integral hull problem. ISSAC ‘23 Proc. 2023 Internat. Sympos. Symbolic Algebraic Comput. (Association for Computing Machinery, New York), 443–451.Google Scholar
• [46] Lasserre JB (2001) An explicit exact SDP relaxation for nonlinear 0-1 programs. Aardal K, Gerards B, eds. Integer Programming Combin. Optim. IPCO 2001, Lecture Notes in Computer Science, vol. 2081 (Springer, Berlin, Heidelberg), 293–303.Google Scholar
• [47] Lasserre JB (2001) Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3):796–817.Crossref, Google Scholar
• [48] Laurent M (2003) A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0-1 programming. Math. Oper. Res. 28(3):470–496.Link, Google Scholar
• [49] Laurent M (2003) Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope. Math. Oper. Res. 28(4):871–883.Link, Google Scholar
• [50] Lee JR, Raghavendra P, Steurer D (2015) Lower bounds on the size of semidefinite programming relaxations. STOC’15 Proc. 47th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 567–576.Google Scholar
• [51] Lee T, Prakash A, Wolf R, Yuen H (2016) On the sum-of-squares degree of symmetric quadratic functions. CCC’16 Proc. 31st Conference on Computational Complexity (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Wadern, Germany), 17:1–17:31.Google Scholar
• [52] Lovász L (1979) On the Shannon capacity of a graph Sherali-Adams relaxations of graph isomorphism polytopes. Discrete Optim. 12:73–97.Google Scholar
• [53] Malkin PN (2014) Sherali–adams relaxations of graph isomorphism polytopes. Discrete Optim. 12:73–97.Crossref, Google Scholar
• [54] Markoff W, Grossmann J (1916) Über polynome, die in einem gegebenen intervalle möglichst wenig von null abweichen. Math. Ann. 77(2):213–258.Crossref, Google Scholar
• [55] Meka R, Potechin A, Wigderson A (2015) Sum-of-squares lower bounds for planted clique. STOC’15 Proc. 47th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 87–96.Google Scholar
• [56] Montanari A (2021) Optimization of the Sherrington-Kirkpatrick Hamiltonian. 2019 IEEE 60th Ann. Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 1417–1433.Google Scholar
• [57] Moore MJ (1968) An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Sci. 15(1):102–109.Link, Google Scholar
• [58] Nesterov Y (2000) Global Quadratic Optimization via Conic Relaxation (Kluwer Academic Publishers, Dordrecht, Netherlands), 363–384.Google Scholar
• [59] O’Donnell R (2014) Analysis of Boolean Functions (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [60] Parisi G (1979) Infinite number of order parameters for spin-glasses. Phys. Rev. Lett. 43(23):1754–1756.Crossref, Google Scholar
• [61] Parrilo P (2000) Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Unpublished PhD thesis, California Institute of Technology, Pasadena, CA.Google Scholar
• [62] Paturi R (1992) On the degree of polynomials that approximate symmetric Boolean functions (preliminary version). STOC’92 Proc. 24th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 468–474.Google Scholar
• [63] Potechin A (2020) Sum of squares bounds for the ordering principle. Saraf S, ed. CCC 2020 35th Comput. Complexity Conf., Leibniz International Proceedings in Informatics (LIPIcs), vol. 169 (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Wadern, Germany), 38:1–38:37.Google Scholar
• [64] Potechin A, Rajendran G (2022) Sub-exponential time sum-of-squares lower bounds for principal components analysis. NIPS’22 Proc. 36th Internat. Conf. Neural Inform. Processing Systems (Curran Associates, Red Hook, NY), 35724–35740.Google Scholar
• [65] Potechin A, Steurer D (2017) Exact tensor completion with sum-of-squares. Conf. Learning Theory (COLT 2017) (Association for Computational Learning, Mountain View, CA), 1619–1673.Google Scholar
• [66] Raghavendra P (2008) Optimal algorithms and inapproximability results for every CSP? STOC’08 Proc. 40th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 245–254.Google Scholar
• [67] Rivlin T (1974) The Chebyshev Polynomials (Wiley, New York).Google Scholar
• [68] Sakaue S, Takeda A, Kim S, Ito N (2017) Exact semidefinite programming relaxations with truncated moment matrix for binary polynomial optimization problems. SIAM J. Optim. 27(1):565–582.Crossref, Google Scholar
• [69] Schramm T, Steurer D (2017) Fast and robust tensor decomposition with applications to dictionary learning. Conf. Learning Theory (COLT 2017) (Association for Computational Learning, Mountain View, CA), 1760–1793.Google Scholar
• [70] Sherstov AA (2009) Approximate inclusion-exclusion for arbitrary symmetric functions. Comput. Complexity 18(2):219–247.Crossref, Google Scholar
• [71] Shor N (1987) Class of global minimum bounds of polynomial functions. Cybernetics 23(6):731–734.Crossref, Google Scholar
• [72] Slot L, Laurent M (2020) Improved convergence analysis of Lasserre’s measure-based upper bounds for polynomial minimization on compact sets. Math. Programming 193:831–871.Crossref, Google Scholar
• [73] Slot L, Laurent M (2023) Sum-of-squares hierarchies for binary polynomial optimization. Math. Programming 197:621–660.Crossref, Google Scholar
• [74] Stengle G (1996) Complexity estimates for the Schmüdgen positivstellensatz. J. Complexity 12(2):167–174.Crossref, Google Scholar
• [75] Steurer D, Tiegel S (2021) Sos degree reduction with applications to clustering and robust moment estimation. Marx D, ed. SODA 2021 Proc. 2021 ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 374–393.Google Scholar
• [76] Thapper J, Zivny S (2017) The power of Sherali-Adams relaxations for general-valued CSPs. SIAM J. Comput. 46(4):1241–1279.Crossref, Google Scholar
• [77] Tulsiani M (2009) CSP gaps and reductions in the Lasserre hierarchy. STOC’09 Proc. 41st Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 303–312.Google Scholar
• [78] Wolf R (2010) A note on quantum algorithms and the minimal degree of ϵ-error polynomials for symmetric functions. Quantum Inform. Comput. 8(10):943–950.Google Scholar