Streaming and Sketching Complexity of CSPs: A survey

Madhu Sudan

Streaming and Sketching Complexity of CSPs: A survey

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2205.02744 v1 pith:4VH2NPFW submitted 2022-05-05 cs.CC cs.DS

Madhu Sudan This is my paper · ORCID

classification cs.CCcs.DS

keywords sketchingcomplexitycspssomestreamingsurveyalgorithmsapproximately

verification ladder T0 review T1 audit T2 compute T3 formal

0 comments

read the original 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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN
cs.ET 2025-02 reject novelty 4.0 of 10

Any finite combinatorial problem with a known logical circuit can be encoded as a tensor network whose contraction defines an explicit, though generally inefficient, solution equation.

Pith tools