A Dichotomy Theorem for Multi-Pass Streaming CSPs

Yumou Fei, Dor Minzer, Shuo Wang · 2025

Read A Dichotomy Theorem for Multi-Pass Streaming CSPs by Yumou Fei, Dor Minzer, Shuo Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-11399.txt.

Introduction

Yumou Fei, Dor Minzer, and Shuo Wang prove a clean split in what streaming algorithms can do, in this 2025 theoretical computer science paper. Their subject is constraint satisfaction problems read as a stream, where an algorithm with tiny memory may pass over the input several times and must judge how satisfiable the instance is.

For every choice of problem parameters, the authors show there is a threshold gap with matching algorithms and lower bounds. Above the threshold, a randomized streaming algorithm using only logarithmic space and constantly many passes succeeds, built from a linear programming relaxation and a distributed approximation scheme. Below it, any algorithm, even randomized and even with polynomially many passes, needs space growing like the cube root of the input size per pass. The hardness side converts integrality gaps of the relaxation into hard instances, analyzed through a communication problem with Fourier methods.

Catalog record

CREATORYumou Fei, Dor Minzer, Shuo Wang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE301 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-11399

Browse the full library · About the Tower of Babel