Nine lower bound conjectures on streaming approximation algorithms for CSPs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918159236202496 |
|---|---|
| author | Singer, Noah G. |
| author_facet | Singer, Noah G. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_10714 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Nine lower bound conjectures on streaming approximation algorithms for CSPs Singer, Noah G. Computational Complexity Data Structures and Algorithms 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. |
| title | Nine lower bound conjectures on streaming approximation algorithms for CSPs |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.10714 |