Cell-probe lower bounds from online communication complexity
From MaRDI portal
Publication:5230357
DOI10.1145/3188745.3188862zbMath1427.68370arXiv1704.06185OpenAlexW2963576976MaRDI QIDQ5230357
Josh Alman, Huacheng Yu, Joshua R. Wang
Publication date: 22 August 2019
Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1704.06185
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Online algorithms; streaming algorithms (68W27) Communication complexity, information complexity (68Q11)
Related Items