Linear space streaming lower bounds for approximating CSPs

DOI10.1145/3519935.3519983arXiv2106.13078OpenAlexW3173219382MaRDI QIDQ6083484

Santhoshini Velusamy, Chi-Ning Chou, Alexander Golovnev, Ameya Velingker

Publication date: 8 December 2023

Published in: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2106.13078

zbMATH Keywords

constraint satisfaction problemsinapproximabilitystreaming algorithmscommunication lower bound

Mathematics Subject Classification ID

Theory of computing (68Qxx)

This page was built for publication: Linear space streaming lower bounds for approximating CSPs