2026-07-22T14:19:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6664 2024-03-06T10:38:37Z ddc:004 open_access

Lower Bounds for CSP Refutation by SDP Hierarchies Mori, Ryuhei Witmer, David constraint satisfaction problems LP and SDP relaxations average-case complexity For a k-ary predicate P, a random instance of CSP(P) with n variables and m constraints is unsatisfiable with high probability when m >= O(n). The natural algorithmic task in this regime is refutation: finding a proof that a given random instance is unsatisfiable. Recent work of Allen et al. suggests that the difficulty of refuting CSP(P) using an SDP is determined by a parameter cmplx(P), the smallest t for which there does not exist a t-wise uniform distribution over satisfying assignments to P. In particular they show that random instances of CSP(P) with m >> n^{cmplx(P)/2} can be refuted efficiently using an SDP. In this work, we give evidence that n^{cmplx(P)/2} constraints are also necessary for refutation using SDPs. Specifically, we show that if P supports a (t-1)-wise uniform distribution over satisfying assignments, then the Sherali-Adams_+ and Lovasz-Schrijver_+ SDP hierarchies cannot refute a random instance of CSP(P) in polynomial time for any m <= n^{t/2-epsilon}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ryuhei Mori and David Witmer 2016 Is Part Of LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2016.41 urn:nbn:de:0030-drops-66645 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.41 eng https://creativecommons.org/licenses/by/3.0/legalcode