2026-07-29T10:45:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16346 2024-03-06T10:57:14Z ddc:004 open_access

Streaming and Sketching Complexity of CSPs: A Survey (Invited Talk) Sudan, Madhu Streaming algorithms Sketching algorithms Dichotomy Communication Complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Madhu Sudan 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.5 urn:nbn:de:0030-drops-163460 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.5 eng https://creativecommons.org/licenses/by/4.0/legalcode