Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs

Noah G. Singer, Madhur Tulsiani, Santhoshini Velusamy

For an arbitrary family of predicates $\mathcal{F}\subseteq \{0,1{\}}^{[q{]}^k}$ and any $\epsilon >0$, we prove a single-pass, linear-space streaming lower bound against the gap promise pro…