TY - GEN

T1 - Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly

AU - Kol, Gillat

AU - Paramonov, Dmitry

AU - Saxena, Raghuvansh R.

AU - Yu, Huacheng

N1 - Publisher Copyright:
© Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, and Huacheng Yu; licensed under Creative Commons License CC-BY 4.0.

PY - 2023/1/1

Y1 - 2023/1/1

N2 - We study boolean constraint satisfaction problems (CSPs) Max-CSPfn 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-CSPfn problem is Θ(∼ ndeg(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 Ω(n2) 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-CSPfn problem as, e.g., negations of variables and repeated constraints are not allowed.

AB - We study boolean constraint satisfaction problems (CSPs) Max-CSPfn 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-CSPfn problem is Θ(∼ ndeg(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 Ω(n2) 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-CSPfn problem as, e.g., negations of variables and repeated constraints are not allowed.

KW - Constraint Satisfaction Problems

KW - Streaming algorithms

UR - http://www.scopus.com/inward/record.url?scp=85147545821&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85147545821&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ITCS.2023.80

DO - 10.4230/LIPIcs.ITCS.2023.80

M3 - Conference contribution

AN - SCOPUS:85147545821

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 14th Innovations in Theoretical Computer Science Conference, ITCS 2023

A2 - Kalai, Yael Tauman

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 14th Innovations in Theoretical Computer Science Conference, ITCS 2023

Y2 - 10 January 2023 through 13 January 2023

ER -