Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.5
URN: urn:nbn:de:0030-drops-163460
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16346/
Sudan, Madhu
Streaming and Sketching Complexity of CSPs: A Survey (Invited Talk)
| pdf-format: |
|
Abstract
In this survey we describe progress over the last decade or so in understanding the complexity of solving constraint satisfaction problems (CSPs) approximately in the streaming and sketching models of computation. After surveying some of the results we give some sketches of the proofs and in particular try to explain why there is a tight dichotomy result for sketching algorithms working in subpolynomial space regime.
BibTeX - Entry
@InProceedings{sudan:LIPIcs.ICALP.2022.5,
author = {Sudan, Madhu},
title = {{Streaming and Sketching Complexity of CSPs: A Survey}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {5:1--5:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-235-8},
ISSN = {1868-8969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16346},
URN = {urn:nbn:de:0030-drops-163460},
doi = {10.4230/LIPIcs.ICALP.2022.5},
annote = {Keywords: Streaming algorithms, Sketching algorithms, Dichotomy, Communication Complexity}
}
| Keywords: | Streaming algorithms, Sketching algorithms, Dichotomy, Communication Complexity | |
| Seminar: | 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 28.06.2022 |
