Linear Space Streaming Lower Bounds for Approximating CSPs

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan +2

We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on $n$ variables taking values in $\{0…