New SDP Roundings and Certifiable Approximation for Cubic Optimization

Jun Ting Hsieh, Pravesh K. Kothari, Lucas Pesenti, Luca Trevisan

Research output: Contribution to conferencePaperpeer-review


We give new rounding schemes for SDP relaxations for the problems of maximizing cubic polynomials over the unit sphere and the n-dimensional hypercube. In both cases, the resulting algorithms yield a O(pn/k) multiplicative approximation in 2O(k) poly(n) time. In particular, we obtain a O(pn/log n) approximation in polynomial time. For the unit sphere, this improves on the rounding algorithms of [5] that need quasi-polynomial time to obtain a similar approximation guarantee. Over the n-dimensional hypercube, our results match the guarantee of a search algorithm of Khot and Naor [19] that obtains a similar approximation ratio via techniques from convex geometry. Unlike their method, our algorithm obtains an upper bound on the integrality gap of SDP relaxations for the problem and as a result, also yields a certificate on the optimum value of the input instance. Our results naturally generalize to homogeneous polynomials of higher degree and imply improved algorithms for approximating satisfiable instances of Max-3SAT. Our main motivation is the stark lack of rounding techniques for SDP relaxations of higher degree polynomial optimization in sharp contrast to a rich theory of SDP roundings for the quadratic case. Our rounding algorithms introduce two new ideas: 1) a new polynomial reweighting based method to round sum-of-squares relaxations of higher degree polynomial maximization problems, and 2) a general technique to compress such relaxations down to substantially smaller SDPs by relying on an explicit construction of certain hitting sets. We hope that our work will inspire improved rounding algorithms for polynomial optimization and related problems.

Original languageEnglish (US)
Number of pages26
StatePublished - 2024
Externally publishedYes
Event35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, United States
Duration: Jan 7 2024Jan 10 2024


Conference35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics


Dive into the research topics of 'New SDP Roundings and Certifiable Approximation for Cubic Optimization'. Together they form a unique fingerprint.

Cite this