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 - 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 -