Cover Image

A Dichotomy Theorem for Multi-Pass Streaming CSPs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Fei, Yumou, Minzer, Dor, Wang, Shuo
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Near-Optimal Space Lower Bounds for Streaming CSPs
by: Fei, Yumou, et al.
Published: (2026)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
by: Fei, Yumou, et al.
Published: (2025)

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
by: Fei, Yumou
Published: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
by: Singer, Noah G., et al.
Published: (2026)

Near Optimal Alphabet-Soundness Tradeoff PCPs
by: Minzer, Dor, et al.
Published: (2024)

Testing Properties of Edge Distributions
by: Fei, Yumou
Published: (2026)

Characterizing Streaming Decidability of CSPs via Non-Redundancy
by: Sharma, Amatya, et al.
Published: (2026)

Linear Space Streaming Lower Bounds for Approximating CSPs
by: Chou, Chi-Ning, et al.
Published: (2021)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
by: Shih, Yu-Sheng, et al.
Published: (2026)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
by: Li, Qian, et al.
Published: (2025)

Sketching approximations and LP approximations for finite CSPs are related
by: Singer, Noah G., et al.
Published: (2025)

Non-Redundancy of Low-Arity Symmetric Boolean CSPs
by: Sharma, Amatya, et al.
Published: (2026)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
by: Singer, Noah G.
Published: (2025)

A New Information Complexity Measure for Multi-pass Streaming with Applications
by: Braverman, Mark, et al.
Published: (2024)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
by: Assadi, Sepehr, et al.
Published: (2024)

Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables
by: Jonsson, Peter, et al.
Published: (2025)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
by: Jansen, Bart M. P., et al.
Published: (2026)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
by: Assadi, Sepehr, et al.
Published: (2024)

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
by: Kim, Eun Jung, et al.
Published: (2022)

A Dichotomy for Maximum PCSPs on Graphs
by: Nakajima, Tamio-Vesa, et al.
Published: (2024)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
by: Brakensiek, Joshua, et al.
Published: (2026)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
by: Wang, Yichuan
Published: (2024)

Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs
by: Abboud, Amir, et al.
Published: (2026)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
by: Jiang, Cheng, et al.
Published: (2026)

Streaming Zero-Knowledge Proofs
by: Cormode, Graham, et al.
Published: (2023)

Asymptotic Rank Speedup Theorems, Revisited
by: Alman, Josh, et al.
Published: (2026)

Semi-Streaming Algorithms for Graph Property Certification
by: Das, Avinandan, et al.
Published: (2025)

Deterministic Independent Sets in the Semi-Streaming Model
by: Ye, Daniel
Published: (2025)

Coloring Graphs with Few Colors in the Streaming Model
by: Assadi, Sepehr, et al.
Published: (2025)

Streaming approximation resistance of every ordering CSP
by: Singer, Noah G., et al.
Published: (2021)

Streaming Complexity Separations for Dense and Sparse Graphs
by: Liu, Yang P., et al.
Published: (2026)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
by: Assadi, Sepehr, et al.
Published: (2025)

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
by: Ciardo, Lorenzo, et al.
Published: (2023)

Single-Pass Streaming CSPs via Two-Tier Sampling
by: Azarmehr, Amir, et al.
Published: (2026)

Dichotomies for Maximum Matching Cut: $H$-Freeness, Bounded Diameter, Bounded Radius
by: Lucke, Felicia, et al.
Published: (2023)

Size Minimization For Multi-Output AND-Functions
by: Armbruster, Susanne
Published: (2024)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
by: Khanna, Sanjeev, et al.
Published: (2025)

A Distributional-Lifting Theorem for PAC Learning
by: Blanc, Guy, et al.
Published: (2025)

Quantum Mass Production Theorems
by: Kretschmer, William
Published: (2022)