Document Open Access Logo

Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs

Authors Albert Atserias , Tuomas Hakoniemi

PDF
Thumbnail PDF

File

LIPIcs.CCC.2019.24.pdf
  • Filesize: 0.5 MB
  • 20 pages

Document Identifiers

Author Details

Albert Atserias
  • Universitat Politècnica de Catalunya, Barcelona, Spain
Tuomas Hakoniemi
  • Universitat Politècnica de Catalunya, Barcelona, Spain

Funding

Both authors were partially funded by European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreement ERC-2014-CoG 648276 (AUTAR) and MICCIN grant TIN2016-76573-C2-1P (TASSAT3).

Acknowledgements

We are grateful to Michal Garlik, Moritz Müller and Aaron Potechin for comments on an earlier version of this paper. We are also grateful to Jakob Nordström for initiating a discussion on the several variants of the definition of monomial size as discussed in Section 2.

Cite AsGet BibTex

Albert Atserias and Tuomas Hakoniemi. Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.CCC.2019.24

Abstract

We show that if a system of degree-k polynomial constraints on n Boolean variables has a Sums-of-Squares (SOS) proof of unsatisfiability with at most s many monomials, then it also has one whose degree is of the order of the square root of n log s plus k. A similar statement holds for the more general Positivstellensatz (PS) proofs. This establishes size-degree trade-offs for SOS and PS that match their analogues for weaker proof systems such as Resolution, Polynomial Calculus, and the proof systems for the LP and SDP hierarchies of Lovász and Schrijver. As a corollary to this, and to the known degree lower bounds, we get optimal integrality gaps for exponential size SOS proofs for sparse random instances of the standard NP-hard constraint optimization problems. We also get exponential size SOS lower bounds for Tseitin and Knapsack formulas. The proof of our main result relies on a zero-gap duality theorem for pre-ordered vector spaces that admit an order unit, whose specialization to PS and SOS may be of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Proof complexity
Keywords
  • Proof complexity
  • semialgebraic proof systems
  • Sums-of-Squares
  • Positivstellensatz
  • trade-offs
  • lower bounds
  • monomial size
  • degree

Metrics

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

References

  1. Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, and Avi Wigderson. Space Complexity in Propositional Calculus. SIAM J. Comput., 31(4):1184-1211, 2002. Preliminary version in STOC 2000. URL: https://doi.org/10.1137/S0097539700366735.
  2. Albert Atserias, Massimo Lauria, and Jakob Nordström. Narrow Proofs May Be Maximally Long. ACM Trans. Comput. Log., 17(3):19:1-19:30, 2016. Preliminary version in CCC 2014. URL: https://doi.org/10.1145/2898435.
  3. Boaz Barak, Fernando G. S. L. Brandão, Aram Wettroth Harrow, Jonathan A. Kelner, David Steurer, and Yuan Zhou. Hypercontractivity, sum-of-squares proofs, and their applications. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 307-326, 2012. URL: https://doi.org/10.1145/2213977.2214006.
  4. Paul Beame, Russell Impagliazzo, Jan Krajíček, Toniann Pitassi, and Pavel Pudlák. Lower Bounds on Hilbert’s Nullstellensatz and Propositional Proofs. Proceedings of the London Mathematical Society, s3-73(1):1-26, 1996. URL: https://doi.org/10.1112/plms/s3-73.1.1.
  5. Paul Beame and Toniann Pitassi. Simplified and Improved Resolution Lower Bounds. In 37th Annual Symposium on Foundations of Computer Science, FOCS '96, Burlington, Vermont, USA, 14-16 October, 1996, pages 274-282, 1996. URL: https://doi.org/10.1109/SFCS.1996.548486.
  6. Eli Ben-Sasson and Avi Wigderson. Short proofs are narrow - resolution made simple. J. ACM, 48(2):149-169, 2001. Preliminary version in STOC 1999. URL: https://doi.org/10.1145/375827.375835.
  7. Maria Luisa Bonet and Nicola Galesi. Optimality of size-width tradeoffs for resolution. Computational Complexity, 10(4):261-276, 2001. URL: https://doi.org/10.1007/s000370100000.
  8. Eden Chlamtac and Madhur Tulsiani. Convex Relaxations and Integrality Gaps. In Miguel F. Anjos and Jean Bernard Lasserre, editors, Handbook on Semidefinite, Conic and Polynomial Optimization, pages 139-169. Springer US, Boston, MA, 2012. URL: https://doi.org/10.1007/978-1-4614-0769-0_6.
  9. Matthew Clegg, Jeff Edmonds, and Russell Impagliazzo. Using the Groebner Basis Algorithm to Find Proofs of Unsatisfiability. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 174-183, 1996. URL: https://doi.org/10.1145/237814.237860.
  10. David A Cox, John Little, and Donal O'Shea. Ideals, Varieties, and Algorithms. Undergraduate Texts in Mathematics. Springer International Publishing, fourth edition, 2015. URL: https://doi.org/10.1007/978-3-319-16721-3.
  11. Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald de Wolf. Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 95-106, 2012. URL: https://doi.org/10.1145/2213977.2213988.
  12. Nicola Galesi and Massimo Lauria. Optimality of size-degree tradeoffs for polynomial calculus. ACM Trans. Comput. Log., 12(1):4:1-4:22, 2010. URL: https://doi.org/10.1145/1838552.1838556.
  13. Dima Grigoriev. Complexity of Positivstellensatz proofs for the knapsack. Computational Complexity, 10(2):139-154, 2001. URL: https://doi.org/10.1007/s00037-001-8192-0.
  14. Dima Grigoriev. Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. Theor. Comput. Sci., 259(1-2):613-622, 2001. URL: https://doi.org/10.1016/S0304-3975(00)00157-2.
  15. Dima Grigoriev, Edward A. Hirsch, and Dmitrii V. Pasechnik. Complexity of Semi-algebraic Proofs. In STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes - Juan les Pins, France, March 14-16, 2002, Proceedings, pages 419-430, 2002. URL: https://doi.org/10.1007/3-540-45841-7_34.
  16. Dima Grigoriev and Nicolai Vorobjov. Complexity of Null- and Positivstellensatz proofs. Annals of Pure and Applied Logic, 113(1):153-160, 2001. First St. Petersburg Conference on Days of Logic and Computability. URL: https://doi.org/10.1016/S0168-0072(01)00055-0.
  17. Russell Impagliazzo, Pavel Pudlák, and Jirí Sgall. Lower Bounds for the Polynomial Calculus and the Gröbner Basis Algorithm. Computational Complexity, 8(2):127-144, 1999. URL: https://doi.org/10.1007/s000370050024.
  18. Dmitry M. Itsykson and Arist A. Kojevnikov. Lower bounds on static Lovász-Schrijver calculus proofs for Tseitin tautologies. Journal of Mathematical Sciences, 145(3):4942-4952, September 2007. Preliminary version in ICALP '06. URL: https://doi.org/10.1007/s10958-007-0329-5.
  19. Cédric Josz and Didier Henrion. Strong duality in Lasserre’s hierarchy for polynomial optimization. Optimization Letters, 10(1):3-10, 2016. URL: https://doi.org/10.1007/s11590-015-0868-5.
  20. Jean-Louis Krivine. Anneaux préordonnés. Journal d'Analyse Mathématique, 12(1):307-326, December 1964. URL: https://doi.org/10.1007/BF02807438.
  21. Jean B. Lasserre. Global Optimization with Polynomials and the Problem of Moments. SIAM Journal on Optimization, 11(3):796-817, 2001. URL: https://doi.org/10.1137/S1052623400366802.
  22. Massimo Lauria and Jakob Nordström. Tight Size-Degree Bounds for Sums-of-Squares Proofs. Computational Complexity, 26(4):911-948, 2017. Preliminary version in CCC 2015. URL: https://doi.org/10.1007/s00037-017-0152-4.
  23. James R. Lee, Prasad Raghavendra, and David Steurer. Lower Bounds on the Size of Semidefinite Programming Relaxations. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 567-576, 2015. URL: https://doi.org/10.1145/2746539.2746599.
  24. James R. Lee, Prasad Raghavendra, David Steurer, and Ning Tan. On the Power of Symmetric LP and SDP Relaxations. In IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014, pages 13-21, 2014. URL: https://doi.org/10.1109/CCC.2014.10.
  25. László Lovász and Alexander Schrijver. Cones of Matrices and Set-Functions and 0-1 Optimization. SIAM Journal on Optimization, 1(2):166-190, 1991. URL: https://doi.org/10.1137/0801013.
  26. Ryan O'Donnell and Yuan Zhou. Approximability and proof complexity. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1537-1556, 2013. URL: https://doi.org/10.1137/1.9781611973105.111.
  27. Pablo A. Parrilo. Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. PhD thesis, California Institute of Technology, 2000. URL: http://resolver.caltech.edu/CaltechETD:etd-05062004-055516.
  28. Vern I. Paulsen and Mark Tomforde. Vector Spaces with an Order Unit. Indiana University Mathematics Journal, 58(3):1319-1359, 2009. URL: http://www.jstor.org/stable/24903253.
  29. Toniann Pitassi and Nathan Segerlind. Exponential Lower Bounds and Integrality Gaps for Tree-Like Lovász-Schrijver Procedures. SIAM J. Comput., 41(1):128-159, 2012. Preliminary version in SODA 2009. URL: https://doi.org/10.1137/100816833.
  30. Aaron Potechin. Sum of squares bounds for the total ordering principle. CoRR, abs/1812.01163, 2018. URL: http://arxiv.org/abs/1812.01163.
  31. Mihai Putinar. Positive Polynomials on Compact Semi-algebraic Sets. Indiana University Mathematics Journal, 42(3):969-984, 1993. URL: http://www.jstor.org/stable/24897130.
  32. Grant Schoenebeck. Linear Level Lasserre Lower Bounds for Certain k-CSPs. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 593-602, 2008. URL: https://doi.org/10.1109/FOCS.2008.74.
  33. Gilbert Stengle. A nullstellensatz and a positivstellensatz in semialgebraic geometry. Mathematische Annalen, 207(2):87-97, June 1974. URL: https://doi.org/10.1007/BF01362149.
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