Document Open Access Logo

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

Authors Adam Kurpisz, Aaron Potechin, Elias Samuel Wirth

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.90.pdf
  • Filesize: 0.77 MB
  • 20 pages

Document Identifiers

Author Details

Adam Kurpisz
  • Department of Mathematics, ETH Zürich, Switzerland
Aaron Potechin
  • Department of Computer Science, University of Chicago, IL, USA
Elias Samuel Wirth
  • Institute of Mathematics, TU Berlin, Germany

Funding

  • Kurpisz, Adam: supported by SNSF project PZ00P2_174117.
  • Potechin, Aaron: supported in part by NSF grant CCF-2008920.

Cite AsGet BibTex

Adam Kurpisz, Aaron Potechin, and Elias Samuel Wirth. SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 90:1-90:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.90

Abstract

We study the rank of the Sum of Squares (SoS) hierarchy over the Boolean hypercube for Symmetric Quadratic Functions (SQFs) in n variables with roots placed in points k-1 and k. Functions of this type have played a central role in deepening the understanding of the performance of the SoS method for various unconstrained Boolean hypercube optimization problems, including the Max Cut problem. Recently, Lee, Prakash, de Wolf, and Yuen proved a lower bound on the SoS rank for SQFs of Ω(√{k(n-k)}) and conjectured the lower bound of Ω(n) by similarity to a polynomial representation of the n-bit OR function. Leveraging recent developments on Chebyshev polynomials, we refute the Lee-Prakash-de Wolf-Yuen conjecture and prove that the SoS rank for SQFs is at most O(√{nk}log(n)). We connect this result to two constrained Boolean hypercube optimization problems. First, we provide a degree O(√n) SoS certificate that matches the known SoS rank lower bound for an instance of Min Knapsack, a problem that was intensively studied in the literature. Second, we study an instance of the Set Cover problem for which Bienstock and Zuckerberg conjectured an SoS rank lower bound of n/4. We refute the Bienstock-Zuckerberg conjecture and provide a degree O(√nlog(n)) SoS certificate for this problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Semidefinite programming
  • Theory of computation → Convex optimization
Keywords
  • symmetric quadratic functions
  • SoS certificate
  • hypercube optimization
  • semidefinite programming

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Arora, S. Rao, and U. V. Vazirani. Expander flows, geometric embeddings and graph partitioning. J. ACM, 56(2):5:1-5:37, 2009. Google Scholar
  2. B. Barak, S. B. Hopkins, J. A. Kelner, P. Kothari, A. Moitra, and A. Potechin. A nearly tight sum-of-squares lower bound for the planted clique problem. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 428-437, 2016. Google Scholar
  3. B. Barak, J. A. Kelner, and D. Steurer. Dictionary learning and tensor decomposition via the sum-of-squares method. In STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 143-151, 2015. Google Scholar
  4. B. Barak and A. Moitra. Noisy tensor completion via the sum-of-squares hierarchy. In COLT 2016, New York, USA, June 23-26, 2016, pages 417-445, 2016. Google Scholar
  5. B. Barak, P. Raghavendra, and D. Steurer. Rounding semidefinite programming hierarchies via global correlation. In FOCS, pages 472-481, 2011. Google Scholar
  6. B. Barak and D. Steurer. Proofs, beliefs, and algorithms through the lens of sum-of-squares, 2016. URL: https://www.sumofsquares.org.
  7. Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan, Venkatesan Guruswami, and Yuan Zhou. Polynomial integrality gaps for strong sdp relaxations of densest k-subgraph. In SODA, 2012. Google Scholar
  8. D. Bienstock and M. Zuckerberg. Subset algebra lift operators for 0-1 integer programming (extended version), 2002. Extended version of: Subset algebra lift operators for 0-1 integer programming - SIAM Journal on Optimization, 1(15): 63-95, 2004. URL: http://www.corc.ieor.columbia.edu/reports/techreports.html.
  9. Grigoriy Blekherman, Pablo A Parrilo, and Rekha R Thomas. Semidefinite optimization and convex algebraic geometry. SIAM, 2012. Google Scholar
  10. K. K. H. Cheung. Computation of the Lasserre ranks of some polytopes. Math. Oper. Res., 32(1):88-94, 2007. Google Scholar
  11. W. Cook and S. Dash. On the matrix-cut rank of polyhedra. Math. Oper. Res., 26(1):19-30, 2001. Google Scholar
  12. Hamza Fawzi, James Saunderson, and Pablo A. Parrilo. Sparse sum-of-squares certificates on finite abelian groups. In 54th IEEE Conference on Decision and Control, CDC 2015, Osaka, Japan, December 15-18, 2015, pages 5909-5914, 2015. URL: https://doi.org/10.1109/CDC.2015.7403148.
  13. Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, and Goutham Rajendran. Sum-of-squares lower bounds for sherrington-kirkpatrick via planted affine planes. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 954-965, 2020. Google Scholar
  14. M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach., 42(6):1115-1145, 1995. Google Scholar
  15. D. Grigoriev. Complexity of positivstellensatz proofs for the knapsack. Comput. Complexity, 10(2):139-154, 2001. Google Scholar
  16. D. Grigoriev, E. A. Hirsch, and D. V. Pasechnik. Complexity of semi-algebraic proofs. In STACS, pages 419-430, 2002. Google Scholar
  17. D. Grigoriev and N. Vorobjov. Complexity of null-and positivstellensatz proofs. Ann. Pure App. Logic, 113(1-3):153-160, 2001. Google Scholar
  18. Dima Grigoriev. Linear lower bound on degrees of positivstellensatz calculus proofs for the parity. Theoretical Computer Science, 259(1-2):613-622, 2001. Google Scholar
  19. V. Guruswami and A. K. Sinop. Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with psd objectives. In FOCS, pages 482-491, 2011. Google Scholar
  20. S. B. Hopkins, T. Schramm, J. Shi, and D. Steurer. Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. In STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 178-191, 2016. Google Scholar
  21. P. Kothari, J. Steinhardt, and D. Steurer. Robust moment estimation and improved clustering via sum of squares. In STOC 2018, 2018. Google Scholar
  22. P. K. Kothari, R. Mori, R. O'Donnell, and D. Witmer. Sum of squares lower bounds for refuting any CSP. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 132-145, 2017. Google Scholar
  23. Dmitriy Kunisky and Afonso S. Bandeira. A tight degree 4 sum-of-squares lower bound for the sherrington-kirkpatrick hamiltonian. CoRR, abs/1907.11686, 2019. URL: http://arxiv.org/abs/1907.11686.
  24. A. Kurpisz, S. Leppänen, and M. Mastrolilli. Sum-of-squares hierarchy lower bounds for symmetric formulations. In Integer Programming and Combinatorial Optimization - 18th International Conference, IPCO 2016, Liège, Belgium, June 1-3, 2016, Proceedings, pages 362-374, 2016. Google Scholar
  25. A. Kurpisz, S. Leppänen, and M. Mastrolilli. Tight sum-of-squares lower bounds for binary polynomial optimization problems. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 78:1-78:14, 2016. Google Scholar
  26. A. Kurpisz, S. Leppänen, and M. Mastrolilli. On the hardest problem formulations for the 0/1 lasserre hierarchy. Math. Oper. Res., 42(1):135-143, 2017. Google Scholar
  27. A. Kurpisz, S. Leppänen, and M. Mastrolilli. An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem. Math. Program., 166(1-2):1-17, 2017. Google Scholar
  28. Adam Kurpisz. Sum-of-squares bounds via boolean function analysis. In ICALP July 9-12, 2019, Patras, Greece, 2019. Google Scholar
  29. J. B. Lasserre. An explicit exact SDP relaxation for nonlinear 0-1 programs. In Integer Programming and Combinatorial Optimization, 8th International IPCO Conference, Utrecht, The Netherlands, June 13-15, 2001, Proceedings, pages 293-303, 2001. Google Scholar
  30. M. Laurent. A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0-1 programming. Math. Oper. Res., 28(3):470-496, 2003. Google Scholar
  31. M. Laurent. Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope. Math. Oper. Res., 28(4):871-883, 2003. Google Scholar
  32. J. R. Lee, P. Raghavendra, and D. Steurer. Lower bounds on the size of semidefinite programming relaxations. In STOC, pages 567-576, 2015. Google Scholar
  33. T. Lee, A. Prakash, R. Wolf, and H. Yuen. On the sum-of-squares degree of symmetric quadratic functions. In 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, pages 17:1-17:31, 2016. Google Scholar
  34. László Lovász. On the shannon capacity of a graph. IEEE Transactions on Information Theory, 25:1-7, 1979. Google Scholar
  35. Raghu Meka, Aaron Potechin, and Avi Wigderson. Sum-of-squares lower bounds for planted clique. In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, pages 87-96, 2015. Google Scholar
  36. M. J. Moore. An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science, 15:102-109, 1968. Google Scholar
  37. Katta G. Murty and Santosh N. Kabadi. Some np-complete problems in quadratic and nonlinear programming. Mathematical Programming, 39(2):117-129, 1987. URL: https://doi.org/10.1007/BF02592948.
  38. Y. Nesterov. Global quadratic optimization via conic relaxation, pages 363-384. Kluwer Academic Publishers, 2000. Google Scholar
  39. P. Parrilo. Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. PhD thesis, California Institute of Technology, 2000. Google Scholar
  40. R. Paturi. On the degree of polynomials that approximate symmetric boolean functions (preliminary version). In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, pages 468-474, 1992. Google Scholar
  41. A. Potechin and D. Steurer. Exact tensor completion with sum-of-squares. In COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, pages 1619-1673, 2017. Google Scholar
  42. Aaron Potechin. Sum of squares bounds for the ordering principle. In Proceedings of the 35th Computational Complexity Conference, pages 1-37, 2020. Google Scholar
  43. T. Rivlin. The chebyshev polynomials. SERBIULA (sistema Librum 2.0), February 1974. Google Scholar
  44. S. Sakaue, A. Takeda, S. Kim, and N. Ito. Exact semidefinite programming relaxations with truncated moment matrix for binary polynomial optimization problems. SIAM Journal on Optimization, 27(1):565-582, 2017. Google Scholar
  45. T. Schramm and D. Steurer. Fast and robust tensor decomposition with applications to dictionary learning. In COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, pages 1760-1793, 2017. Google Scholar
  46. N. Shor. Class of global minimum bounds of polynomial functions. Cybernetics, 23(6):731-734, 1987. Google Scholar
  47. Lucas Slot and Monique Laurent. Improved convergence analysis of lasserre’s measure-based upper bounds for polynomial minimization on compact sets. CoRR, 2019. URL: https://doi.org/10.1007/s10107-020-01468-3.
  48. J. Thapper and S. Zivny. The power of sherali-adams relaxations for general-valued csps. SIAM J. Comput., 46(4):1241-1279, 2017. Google Scholar
  49. Madhur Tulsiani. Csp gaps and reductions in the lasserre hierarchy. In STOC, pages 303-312, 2009. Google Scholar
  50. R. Wolf. A note on quantum algorithms and the minimal degree of ε-error polynomials for symmetric functions. Quantum Information & Computation, 8(10):943-950, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact