Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds
From MaRDI portal
Publication:5230355
DOI10.1145/3188745.3188790zbMath1428.68132arXiv1703.03575OpenAlexW2604958820MaRDI QIDQ5230355
Huacheng Yu, Omri Weinstein, Kasper Green Larsen
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/1703.03575
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Communication complexity, information complexity (68Q11)
Related Items (5)
A logarithmic lower bound for oblivious RAM (for all Parameters) ⋮ Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ Lower bounds for matrix factorization ⋮ Lower bounds for matrix factorization ⋮ Lower bounds for encrypted multi-maps and searchable encryption in the leakage cell probe model
This page was built for publication: Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds
