2026-07-25T14:52:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17583 2024-03-06T10:59:58Z ddc:004 open_access

Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly Kol, Gillat Paramonov, Dmitry Saxena, Raghuvansh R. Yu, Huacheng Streaming algorithms Constraint Satisfaction Problems We study boolean constraint satisfaction problems (CSPs) Max-CSP^f_n for all predicates f: {0,1}^k → {0,1}. In these problems, given an integer v and a list of constraints over n boolean variables, each obtained by applying f to a sequence of literals, we wish to decide if there is an assignment to the variables that satisfies at least v constraints. We consider these problems in the streaming model, where the algorithm makes a small number of passes over the list of constraints. Our first and main result is the following complete characterization: For every predicate f, the streaming space complexity of the Max-CSP^f_n problem is Θ̃(n^deg(f)), where deg(f) is the degree of f when viewed as a multilinear polynomial. While the upper bound is obtained by a (very simple) one-pass streaming algorithm, our lower bound shows that a better space complexity is impossible even with constant-pass streaming algorithms. Building on our techniques, we are also able to get an optimal Ω(n²) lower bound on the space complexity of constant-pass streaming algorithms for the well studied Max-CUT problem, even though it is not technically a Max-CSP^f_n problem as, e.g., negations of variables and repeated constraints are not allowed. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gillat Kol and Dmitry Paramonov and Raghuvansh R. Saxena and Huacheng Yu 2023 Is Part Of LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2023.80 urn:nbn:de:0030-drops-175837 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.80 eng https://creativecommons.org/licenses/by/4.0/legalcode