{"ID":2871437,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.11399","arxiv_id":"2509.11399","title":"A Dichotomy Theorem for Multi-Pass Streaming CSPs","abstract":"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 $\\mathcal{F}$ of $k$-ary predicates over $Σ$ and any $c\\in (0,1)$, there exists $0\u003cs\\leq c$ such that: 1. For any $\\varepsilon\u003e0$ there is a constant pass, $O_{\\varepsilon}(\\log n)$-space randomized streaming algorithm solving the promise problem $\\text{MaxCSP}(\\mathcal{F})[c,s-\\varepsilon]$. 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-\\varepsilon$ with probability at least $2/3$. 2. For all $\\varepsilon\u003e0$, any $p$-pass (even randomized) streaming algorithm that solves the promise problem $\\text{MaxCSP}(\\mathcal{F})[c,s+\\varepsilon]$ must use $Ω_{\\varepsilon}(n^{1/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, Velusamy, J.ACM 2024].","short_abstract":"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 $\\mathcal{F}$ of $k$-ary predicates over $Σ$ and any $c\\in (0,1)$, there exists $0\u003cs\\leq c$ such that: 1. For any $...","url_abs":"https://arxiv.org/abs/2509.11399","url_pdf":"https://arxiv.org/pdf/2509.11399v2","authors":"[\"Yumou Fei\",\"Dor Minzer\",\"Shuo Wang\"]","published":"2025-09-14T19:22:22Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DS\"]","methods":"[]","has_code":false}