Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR22-065 | 5th May 2022 17:17

Streaming and Sketching Complexity of CSPs: A survey

RSS-Feed




Revision #1
Authors: Madhu Sudan
Accepted on: 5th May 2022 17:17
Downloads: 157
Keywords: 


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.



Changes to previous version:

Minor errors corrected.


Paper:

TR22-065 | 3rd May 2022 22:55

Streaming and Sketching Complexity of CSPs: A survey





TR22-065
Authors: Madhu Sudan
Publication: 3rd May 2022 22:56
Downloads: 189
Keywords: 


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.



ISSN 1433-8092 | Imprint