Document Open Access Logo

SOS Lower Bounds with Hard Constraints: Think Global, Act Local

Authors Pravesh K. Kothari, Ryan O'Donnell, Tselil Schramm

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.49.pdf
  • Filesize: 0.55 MB
  • 21 pages

Document Identifiers

Author Details

Pravesh K. Kothari
  • Department of Computer Science, Princeton University and Institute for Advanced Study, Princeton, USA
Ryan O'Donnell
  • Department of Computer Science, Carnegie Mellon University, Pittsburgh, USA
Tselil Schramm
  • Department of Computer Science, Harvard and MIT, Cambridge, USA

Funding

  • O'Donnell, Ryan: Some work performed at the Boğaziçi University Computer Engineering Department, supported by Marie Curie International Incoming Fellowship project number 626373. Also supported by NSF grants CCF-1618679, CCF-1717606. This material is based upon work supported by the National Science Foundation under grant numbers listed above. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation (NSF).
  • Schramm, Tselil: This work was partly supported by an NSF Graduate Research Fellowship (1106400), and also by a Simons Institute Fellowship.

Cite AsGet BibTex

Pravesh K. Kothari, Ryan O'Donnell, and Tselil Schramm. SOS Lower Bounds with Hard Constraints: Think Global, Act Local. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 49:1-49:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ITCS.2019.49

Abstract

Many previous Sum-of-Squares (SOS) lower bounds for CSPs had two deficiencies related to global constraints. First, they were not able to support a "cardinality constraint", as in, say, the Min-Bisection problem. Second, while the pseudoexpectation of the objective function was shown to have some value beta, it did not necessarily actually "satisfy" the constraint "objective = beta". In this paper we show how to remedy both deficiencies in the case of random CSPs, by translating global constraints into local constraints. Using these ideas, we also show that degree-Omega(sqrt{n}) SOS does not provide a (4/3 - epsilon)-approximation for Min-Bisection, and degree-Omega(n) SOS does not provide a (11/12 + epsilon)-approximation for Max-Bisection or a (5/4 - epsilon)-approximation for Min-Bisection. No prior SOS lower bounds for these problems were known.

Subject Classification

ACM Subject Classification
  • Theory of computation → Semidefinite programming
  • Theory of computation → Randomness, geometry and discrete structures
Keywords
  • sum-of-squares hierarchy
  • random constraint satisfaction problems

Metrics

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

Related Versions

References

  1. Per Austrin and Johan Håstad. Randomly supported independence and resistance. SIAM Journal on Computing, 40(1):1-27, 2011. Google Scholar
  2. Boaz Barak, Fernando Brandão, Aram Harrow, Jonathan Kelner, David Steurer, and Yuan Zhou. Hypercontractivity, Sum-of-Squares Proofs, and their Applications. In Proc. of the 44th Annual ACM Symposium on Theory of Computing, pages 307-326, 2012. Google Scholar
  3. Boaz Barak, Siu On Chan, and Pravesh Kothari. Sum of Squares Lower Bounds from Pairwise Independence. In Proc. of the 47th Annual ACM Symposium on Theory of Computing, pages 97-106, 2015. Google Scholar
  4. Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh Kothari, Ankur Moitra, and Aaron Potechin. A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. In Proc. of the 57th Annual IEEE Symposium on Foundations of Computer Science, 2016. Google Scholar
  5. Boaz Barak and David Steurer. Proofs, beliefs, and algorithms through the lens of sum-of-squares, 2016. URL: http://sumofsquares.org/public/index.html.
  6. Irit Dinur, Ehud Friedgut, Guy Kindler, and Ryan O'Donnell. On the Fourier tails of bounded functions over the discrete cube. Israel Journal of Mathematics, 160(1):389-412, 2007. Google Scholar
  7. Uriel Feige. Relations between average case complexity and approximation complexity. In Proc. of the 34th Annual ACM Symposium on Theory of Computing, pages 543-543, 2002. Google Scholar
  8. Dima Grigoriev. Complexity of Positivstellensatz proofs for the knapsack. Computational Complexity, 10(2):139-154, 2001. Google Scholar
  9. 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
  10. Dima Grigoriev, Edward Hirsch, and Dmitrii Pasechnik. Complexity of semialgebraic proofs. Moscow Mathematical Journal, 2(4):647-679, 2002. Google Scholar
  11. Venkatesan Guruswami, Ali Kemal Sinop, and Yuan Zhou. Constant factor Lasserre integrality gaps for graph partitioning problems. SIAM Journal on Optimization, 24(4):1698-1717, 2014. Google Scholar
  12. Johan Håstad. Some optimal inapproximability results. Journal of the ACM, 48(4):798-859, 2001. Google Scholar
  13. Subhash Khot. Ruling out PTAS for Graph Min-Bisection, Dense k-Subgraph, and Bipartite Clique. SIAM Journal on Computing, 36(4):1025-1071, 2006. Google Scholar
  14. Pravesh Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer. Sum of squares lower bounds for refuting any CSP. In Proc. of the 49th Annual ACM Symposium on Theory of Computing, pages 132-145, 2017. Google Scholar
  15. Pravesh K. Kothari and Ruta Mehta. Sum-of-squares meets Nash: lower bounds for finding any equilibrium. In Proc. of the 50th Annual ACM Symposium on Theory of Computing, pages 1241-1248, 2018. Google Scholar
  16. Ryan O'Donnell. SOS is not obviously automatizable, even approximately. In Proc. of the 8th Annual Innovations in Theoretical Computer Science conference, 2017. Google Scholar
  17. Ryan O'Donnell and John Wright. A new point of NP-hardness for Unique-Games. In Proc. of the 44th Annual ACM Symposium on Theory of Computing, pages 289-306, 2012. Google Scholar
  18. Prasad Raghavendra and Benjamin Weitz. On the Bit Complexity of Sum-of-Squares Proofs. Technical report, arXiv, 2017. URL: http://arxiv.org/abs/1702.05139.
  19. Grant Schoenebeck. Linear Level Lasserre Lower Bounds for Certain k-CSPs. In Proc. of the 49th Annual IEEE Symposium on Foundations of Computer Science, pages 593-602, 2008. Google Scholar
  20. Luca Trevisan, Gregory Sorkin, Madhu Sudan, and David Williamson. Gadgets, Approximation, and Linear Programming. SIAM Journal on Computing, 29(6):2074-2097, 2000. Google Scholar
  21. Madhur Tulsiani. CSP gaps and reductions in the Lasserre hierarchy. In Proc. of the 41st Annual ACM Symposium on Theory of Computing, pages 303-312, 2009. 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