Characterizing the multi-pass streaming complexity for solving Boolean CSPs exactly

DOI10.4230/LIPICS.ITCS.2023.80MaRDI QIDQ6610352zbMATH OpenFDO

Authors Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Huacheng Yu

Publication date 25 September 2024

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2023.80

zbMATH Keywords

constraint satisfaction problemsstreaming algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(2)

• Polynomial pass semi-streaming lower bounds for k-cores and degeneracy
• Sketching approximability of all finite CSPs

This page was built for publication: Characterizing the multi-pass streaming complexity for solving Boolean CSPs exactly

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6610352)