2025/09/14 by Fei, Yumou, Minzer, Dor, Wang, Shuo · 4 citations
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2509.11399
We show a dichotomy result for p-pass streaming algorithms for all CSPs and for up to polynomially many passes. More precisely, we prove that for any arity parameter k, finite alphabet Σ, collection F of k-ary predicates over Σ and any c∈ (0,1), there exists 00 there is a constant pass, Oε(log n)-space randomized streaming algorithm solving the promise problem MaxCSP(F)[c,s-ε]. That is, the algorithm accepts inputs with value at least c with probability at least 2/3, and rejects inputs with value at most s-ε with probability at least 2/3. 2. For all ε>0, any p-pass (even randomized) streaming algorithm that solves the promise problem MaxCSP(F)[c,s+ε] must use Ωε(n1/3/p) space. Our approximation algorithm is based on a certain linear-programming relaxation of the CSP and on a distributed algorithm that approximates its value. This part builds on the works [Yoshida, STOC 2011] and [Saxena, Singer, Sudan, Velusamy, SODA 2025]. For our hardness result we show how to translate an integrality gap of the linear program into a family of hard instances, which we then analyze via studying a related communication complexity problem. That analysis is based on discrete Fourier analysis and builds on a prior work of the authors and on the work [Chou, Golovnev, Sudan, Velingker, Velusamy, J.ACM 2024].