TY - GEN
T1 - SOS lower bounds with hard constraints
T2 - 10th Innovations in Theoretical Computer Science, ITCS 2019
AU - Kothari, Pravesh K.
AU - O’Donnell, Ryan
AU - Schramm, Tselil
N1 - Funding Information:
The authors very much thank Sangxia Huang and David Witmer for their contributions to the early stages of this research. Thanks also to Svante Janson for discussions concerning contiguity of random graph models. We also greatfully acknowledge comments on the manuscript from Johan H?stad as well as several anonymous reviewers. 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). This work was partly supported by an NSF Graduate Research Fellowship (1106400), and also by a Simons Institute Fellowship.
Funding Information:
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). 2 This work was partly supported by an NSF Graduate Research Fellowship (1106400), and also by a Simons Institute Fellowship.
Funding Information:
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-
Publisher Copyright:
© Pravesh Kothari, Ryan O’Donnell, and Tselil Schramm.
PY - 2019/1/1
Y1 - 2019/1/1
N2 - 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.
AB - 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.
KW - Random constraint satisfaction problems
KW - Sum-of-squares hierarchy
UR - http://www.scopus.com/inward/record.url?scp=85069504564&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85069504564&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITCS.2019.49
DO - 10.4230/LIPIcs.ITCS.2019.49
M3 - Conference contribution
AN - SCOPUS:85069504564
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 10th Innovations in Theoretical Computer Science, ITCS 2019
A2 - Blum, Avrim
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 10 January 2019 through 12 January 2019
ER -