Showing cs.CCShow all
2 papers · 1 filter
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…