Linear space streaming lower bounds for approximating CSPs

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,…, q −1}, we prove that improving over the trivial approximability by a factor of q requires Ω( n ) space even on instances with O ( n ) constraints. We also identify a broad subclass of problems for which any improvement over the trivial approximability requires Ω( n ) space. The key technical core is an optimal, q −( k −1) -inapproximability for the Max k -LIN-mod q problem, which is the Max CSP problem where every constraint is given by a system of k −1 linear equations mod q over k variables.

Authors

• Chi-Ning Chou
• Alexander Golovnev
• Madhu Sudan 0001
• Ameya Velingker
• Santhoshini Velusamy

Keywords

• constraint satisfaction problems
• communication lower bound
• inapproximability
• streaming algorithms