paper

Nine lower bound conjectures on streaming approximation algorithms for CSPs

arXiv:2510.10714

Abstract

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 by this recent progress, we collate nine conjectural lower bounds against streaming algorithms for CSPs, some of which appear here for the first time.

12 pages, to appear in SIGACT News Open Problems column

Nine lower bound conjectures on streaming approximation algorithms for CSPs · wovepaper