{"ID":2856851,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.10714","arxiv_id":"2510.10714","title":"Nine lower bound conjectures on streaming approximation algorithms for CSPs","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.","short_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 f...","url_abs":"https://arxiv.org/abs/2510.10714","url_pdf":"https://arxiv.org/pdf/2510.10714v1","authors":"[\"Noah G. Singer\"]","published":"2025-10-12T17:34:20Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DS\"]","methods":"[]","has_code":false}