Streaming space understanding for Boolean constraint problems with deletions

A New Characterization of Streaming Decidability of Boolean CSPs Under Deletions

Computational Complexity

Summary

This work studies how much memory is needed to decide if certain logic-based puzzles, involving variables that can be true or false, can be solved when the puzzles are given as a long sequence of steps that add or remove conditions. The authors give a precise rule, based on a mathematical property related to polynomials, that tells how this memory need grows with the puzzle size. They also show the difference between only adding conditions and allowing both adding and removing, with the latter requiring more memory. This helps explain the complexity of solving these puzzles in real-time scenarios with changing data.

What this means in practice

  • For database engineers: Manage and verify large streaming data constraints that change over time with more accurate memory bounds.
  • For network protocol developers: Design streaming protocols that maintain satisfiability under both addition and deletion of constraints with memory guarantees.

A theory result. No direct application yet.

Authors

Aditya Bandekar, Amatya Sharma, Santhoshini Velusamy

Abstract

We characterize the single-pass streaming space complexity of Boolean CSP satisfiability in the strict-turnstile model for every fixed constraint language $Γ$ of $k$-ary Boolean relations that is not trivially satisfiable. Constraints can be inserted or deleted with nonnegative multiplicities; satisfiability is decided for those remaining at the end. While Sharma and Velusamy [ESA 2026] characterized insertion-only complexity via non-redundancy (up to logarithmic factors), we show that strict-turnstile complexity is governed by the integer capturing degree. For $R\subseteq\{0,1\}^k$, let $d_R$ be the minimum degree of an integer-coefficient polynomial vanishing exactly on $R$ over the Boolean hypercube, and set $d_Γ=\max_{R\inΓ}d_R$. On polynomial-length streams, we obtain an $O_k(n^{d_Γ}\operatorname{polylog} n)$-space randomized algorithm and an $Ω_k(n^{d_Γ}/\log n)$ lower bound for all algorithms. Moreover, our algorithm outputs a sparse instance preserving every satisfying assignment. This yields, to our knowledge, the first insertion-only versus turnstile separation for streaming CSPs. It also differs from the Fourier-degree characterization of exact optimization by Kol, Paramonov, Saxena, and Yu [ITCS 2023]. For $k\ge3$, $k$-XOR with literals has three distinct space complexities: $\widetildeΘ(n)$ for insertion-only satisfiability, $\widetildeΘ(n^{\lceil k/2\rceil})$ for strict-turnstile satisfiability, and $\widetildeΘ(n^k)$ for exact optimization in either model.