3 papers
cs.CC2026
Near-Optimal Space Lower Bounds for Streaming CSPs
Yumou Fei, Dor Minzer, Shuo Wang
In a streaming constraint satisfaction problem (streaming CSP), a -pass algorithm receives the constraints of an instance sequentially, making passes over the input in a fix…
cs.CC2026
A Dichotomy Theorem for Multi-Pass Streaming CSPs
Yumou Fei, Dor Minzer, Shuo Wang
We show a dichotomy result for -pass streaming algorithms for all CSPs and for up to polynomially many passes. More precisely, we prove that for any arity parameter , finite…
cs.DS2025
Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
Yumou Fei, Dor Minzer, Shuo Wang
In the Max-Cut problem in the streaming model, an algorithm is given the edges of an unknown graph in some fixed order, and its goal is to approximate the size of the l…