Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-148 | 12th October 2025 19:48

Nine lower bound conjectures on streaming approximation algorithms for CSPs

RSS-Feed




TR25-148
Authors: Noah Singer
Publication: 17th October 2025 12:18
Downloads: 63
Keywords: 


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.



ISSN 1433-8092 | Imprint