Document Open Access Logo

Sum-Of-Squares Bounds via Boolean Function Analysis

Author Adam Kurpisz

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2019.79.pdf
  • Filesize: 497 kB
  • 15 pages

Document Identifiers

Subject Classification

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

Metrics

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

Abstract

We introduce a method for proving bounds on the SoS rank based on Boolean Function Analysis and Approximation Theory. We apply our technique to improve upon existing results, thus making progress towards answering several open questions.
We consider two questions by Laurent. First, finding what is the SoS rank of the linear representation of the set with no integral points. We prove that the SoS rank is between ceil[n/2] and ceil[~ n/2 +sqrt{n log{2n}} ~]. Second, proving the bounds on the SoS rank for the instance of the Min Knapsack problem. We show that the SoS rank is at least Omega(sqrt{n}) and at most ceil[{n+ 4 ceil[sqrt{n} ~]}/2]. Finally, we consider the question by Bienstock regarding the instance of the Set Cover problem. For this problem we prove the SoS rank lower bound of Omega(sqrt{n}).

Cite As Get BibTex

Adam Kurpisz. Sum-Of-Squares Bounds via Boolean Function Analysis. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 79:1-79:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.79

Author Details

Adam Kurpisz
  • ETH Zürich, Department of Mathematics, Rämistrasse 101, 8092 Zürich, Switzerland

Funding

Supported by SNSF project PZ00P2_174117.

Acknowledgements

I would like to express my gratitude to Markus Schweighofer for fruitful discussions.

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. M. Hossein Bateni, M. Charikar, and V. Guruswami. MaxMin allocation via degree lower-bounded arborescences. In STOC, pages 543-552, 2009. Google Scholar
  8. D. Bienstock and M. Zuckerberg. Subset Algebra Lift Operators for 0-1 Integer Programming. SIAM Journal on Optimization, 15(1):63-95, 2004. Google Scholar
  9. S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, New York, NY, USA, 2004. Google Scholar
  10. H. Chernof. A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations. Ann. Math. Statist., 23(4):493-507, December 1952. Google Scholar
  11. K. K. H. Cheung. Computation of the Lasserre Ranks of Some Polytopes. Math. Oper. Res., 32(1):88-94, 2007. Google Scholar
  12. E. Chlamtac. Approximation Algorithms Using Hierarchies of Semidefinite Programming Relaxations. In FOCS, pages 691-701, 2007. Google Scholar
  13. E. Chlamtac and G. Singh. Improved Approximation Guarantees through Higher Levels of SDP Hierarchies. In APPROX-RANDOM, pages 49-62, 2008. Google Scholar
  14. E. Chlamtac and M. Tulsiani. Convex Relaxations and Integrality Gaps, pages 139-169. Springer US, Boston, MA, 2012. Google Scholar
  15. W. Cook and S. Dash. On the matrix-cut rank of polyhedra. Math. Oper. Res., 26(1):19-30, 2001. Google Scholar
  16. G. Cornuéjols and Y. Li. On the Rank of Mixed 0, 1 Polyhedra. In Proceedings of the 8th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2001, Utrecht, The Netherlands, pages 71-77, 2001. Google Scholar
  17. M. Cygan, F. Grandoni, and M. Mastrolilli. How to Sell Hyperedges: The Hypermatching Assignment Problem. In SODA, pages 342-351, 2013. Google Scholar
  18. W. F. de la Vega and C. Kenyon-Mathieu. Linear programming relaxations of maxcut. In SODA, pages 53-61, 2007. Google Scholar
  19. M. X. Goemans and L. Tunçel. When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures? Math. Oper. Res., 26(4):796-815, 2001. Google Scholar
  20. 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
  21. D. Grigoriev. Complexity of Positivstellensatz proofs for the knapsack. Comput. Complexity, 10(2):139-154, 2001. Google Scholar
  22. D. Grigoriev, E. A. Hirsch, and D. V. Pasechnik. Complexity of Semi-algebraic Proofs. In STACS, pages 419-430, 2002. Google Scholar
  23. D. Grigoriev and N. Vorobjov. Complexity of Null-and Positivstellensatz proofs. Ann. Pure App. Logic, 113(1-3):153-160, 2001. Google Scholar
  24. 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
  25. 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
  26. P. Kothari, J. Steinhardt, and D. Steurer. Robust Moment Estimation and Improved Clustering via Sum of Squares. In STOC 2018, 2018. Google Scholar
  27. 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
  28. 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
  29. 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
  30. 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
  31. 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
  32. 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
  33. 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
  34. 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
  35. M. Laurent. Sums of squares, moment matrices and optimization over polynomials. In Emerging applications of algebraic geometry, volume 149 of IMA Vol. Math. Appl., pages 157-270. Springer, New York, 2009. Google Scholar
  36. 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
  37. 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
  38. A. Magen and M. Moharrami. Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy. In APPROX-RANDOM, pages 258-271, 2009. Google Scholar
  39. M. Mastrolilli. High Degree Sum of Squares Proofs, Bienstock-Zuckerberg Hierarchy and CG Cuts. In Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, pages 405-416, 2017. Google Scholar
  40. 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
  41. Y. Nesterov. Global quadratic optimization via conic relaxation, pages 363-384. Kluwer Academic Publishers, 2000. Google Scholar
  42. R. O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. Google Scholar
  43. P. Parrilo. Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. PhD thesis, California Institute of Technology, 2000. Google Scholar
  44. 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
  45. 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
  46. P. Raghavendra and N. Tan. Approximating CSPs with global cardinality constraints using SDP hierarchies. In SODA, pages 373-387, 2012. Google Scholar
  47. T. Rivlin. The chebyshev polynomials. SERBIULA (sistema Librum 2.0), February 1974. Google Scholar
  48. 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
  49. 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
  50. Alexander A. Sherstov. Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions. Computational Complexity, 18(2):219-247, 2009. URL: http://dx.doi.org/10.1007/s00037-009-0274-4.
  51. N. Shor. Class of global minimum bounds of polynomial functions. Cybernetics, 23(6):731-734, 1987. Google Scholar
  52. 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
  53. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact