SOS lower bounds with hard constraints: Think global, act local

Pravesh K. Kothari, Ryan O’Donnell, Tselil Schramm

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 β, it did not necessarily actually “satisfy” the constraint “objective = β”. 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-Ω(Formula presented.) SOS does not provide a (Formula presented.)-approximation for Min-Bisection, and degree-Ω(n) SOS does not provide a (Formula presented.)-approximation for Max-Bisection or a (Formula presented.)-approximation for Min-Bisection. No prior SOS lower bounds for these problems were known.

Original languageEnglish (US)
Title of host publication10th Innovations in Theoretical Computer Science, ITCS 2019
EditorsAvrim Blum
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770958
DOIs
StatePublished - Jan 1 2019
Event10th Innovations in Theoretical Computer Science, ITCS 2019 - San Diego, United States
Duration: Jan 10 2019Jan 12 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume124
ISSN (Print)1868-8969

Conference

Conference10th Innovations in Theoretical Computer Science, ITCS 2019
CountryUnited States
CitySan Diego
Period1/10/191/12/19

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Random constraint satisfaction problems
  • Sum-of-squares hierarchy

Cite this

Kothari, P. K., O’Donnell, R., & Schramm, T. (2019). SOS lower bounds with hard constraints: Think global, act local. In A. Blum (Ed.), 10th Innovations in Theoretical Computer Science, ITCS 2019 [49] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 124). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ITCS.2019.49