Polynomial pass lower bounds for graph streaming algorithms

DOI10.1145/3313276.3316361zbMath1433.68617arXiv1904.04720OpenAlexW2953264324MaRDI QIDQ5212768

Sanjeev Khanna, Sepehr Assadi, Yu Chen

Publication date: 30 January 2020

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

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

zbMATH Keywords

lower boundscommunication complexitygraph streaming

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Online algorithms; streaming algorithms (68W27) Communication complexity, information complexity (68Q11)

Related Items

Unnamed Item