2026-08-18T05:51:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10142 2024-03-06T10:45:29Z ddc:004 open_access

SOS Lower Bounds with Hard Constraints: Think Global, Act Local Kothari, Pravesh K. O'Donnell, Ryan Schramm, Tselil sum-of-squares hierarchy random constraint satisfaction problems 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pravesh K. Kothari and Ryan O'Donnell and Tselil Schramm 2019 Is Part Of LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2019.49 urn:nbn:de:0030-drops-101420 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.49 eng https://creativecommons.org/licenses/by/3.0/legalcode