Showing cs.CCShow all
3 papers · 1 filter
cs.CC2026
Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
Noah G. Singer, Madhur Tulsiani, Santhoshini Velusamy
For an arbitrary family of predicates and any , we prove a single-pass, linear-space streaming lower bound against the gap promise pr…
cs.CC2025
Nine lower bound conjectures on streaming approximation algorithms for CSPs
Noah G. Singer
In this column, we overview recent progress by many authors on understanding the approximability of constraint satisfaction problems (CSPs) in low-space streaming models. Inspired…
cs.CC2025
Sketching approximations and LP approximations for finite CSPs are related
Noah G. Singer, Madhur Tulsiani, Santhoshini Velusamy
We identify a connection between the approximability of CSPs in two models: (i) sublinear space streaming algorithms, and (ii) the basic LP relaxation. We show that whenever the ba…