A Dichotomy Theorem for Multi-Pass Streaming CSPs
arXiv:2509.11399v2 Announce Type: replace-cross 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 $\Sigma$, collection $\mathcal{F}$ of $k$-ary predicates over $\Sigma$ and any $c\in (0,1)$, there exists $0 0$ 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>0$, any $p$-pass (even randomized) streaming algorithm that solves the
View PDF
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 $\Sigma$, collection $\mathcal{F}$ of $k$-ary predicates over $\Sigma$ and any $c\in (0,1)$, there exists $0 1. For any $\varepsilon>0$ 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>0$, any $p$-pass (even randomized) streaming algorithm that solves the promise problem $\text{MaxCSP}(\mathcal{F})[c,s+\varepsilon]$ must use $\Omega_{\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, this http URL 2024].
Comments: various minor errors corrected in the second version
Subjects:
Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
Cite as: arXiv:2509.11399 [cs.CC]
(or arXiv:2509.11399v2 [cs.CC] for this version)
https://doi.org/10.48550/arXiv.2509.11399
arXiv-issued DOI via DataCite
Submission history
From: Yumou Fei [view email] [v1] Sun, 14 Sep 2025 19:22:22 UTC (99 KB) [v2] Wed, 1 Apr 2026 22:02:29 UTC (96 KB)
Sign in to highlight and annotate this article
Conversation starters
Daily AI Digest
Get the top 5 AI stories delivered to your inbox every morning.
More about
announceanalysisstudy
60% of Consumers Want Approval Gates for AI Spending. Who Builds Them?
Visa just published a study of 2,000 consumers on AI agents and spending. The finding that should dominate every conversation about agentic commerce: 60% of respondents want human approval gates before an AI agent makes purchases on their behalf. Only 27% are comfortable with unlimited AI spending authority. Thirty-six percent say they would trust an AI agent backed by their bank. Twenty-eight percent would trust an independent agent. The paper's own summary: "Trust is the adoption switch." This is empirical confirmation of something that was structurally obvious. The infrastructure to move money is almost ready. The infrastructure to decide whether money should move does not exist. The asymmetry Two days ago, the x402 Foundation launched under the Linux Foundation. Twenty-two founding mem
Precision Clip Selection: How AI Suggests Your In and Out Points
The Problem with Finding the Good Bits You’ve got 90 minutes of interview footage or 2 hours of a chaotic vlog. Manually scrubbing through it all to find usable clips is a massive time sink. It’s tedious, inconsistent, and keeps you from the creative edit. The Core Principle: Context-Aware Chunking The breakthrough isn't just AI hearing words—it’s understanding context . Forget simple sentence detection. Modern tools use linguistic analysis to detect sentence completion, topic shifts, questions, and even punchlines. This allows for Context-Aware Chunking , where the AI groups continuous thoughts, not just audio pauses. For example, in a podcast, it can identify a guest’s entire anecdote—from setup to conclusion—and log it from start to finish as a single, perfectly timed clip candidate. Th
Autonomous Revolution: How AI Agents are Redefining Blockchain's Future
Autonomous Revolution: How AI Agents are Redefining Blockchain's Future The convergence of artificial intelligence and blockchain technology is no longer a futuristic pipe dream; it's a rapidly unfolding reality. As developers and innovators push the boundaries of decentralized systems, the integration of AI agents in blockchain is emerging as a critical catalyst for enhanced efficiency, security, and user experience. This article delves into the transformative potential of these intelligent entities, exploring how they are poised to reshape the crypto landscape and unlock unprecedented levels of automation and intelligence within Web3. The Symbiotic Relationship: AI Enhancing Decentralization Blockchain's core tenets of decentralization, immutability, and transparency are powerful, but th
Knowledge Map
Connected Articles — Knowledge Graph
This article is connected to other articles through shared AI topics and tags.
Discussion
Sign in to join the discussion
No comments yet — be the first to share your thoughts!