The cell probe complexity of dynamic range counting
From MaRDI portal
Publication:5415467
DOI10.1145/2213977.2213987zbMath1286.68104arXiv1105.5933OpenAlexW1988508518MaRDI QIDQ5415467
Publication date: 13 May 2014
Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1105.5933
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)
Related Items (18)
A logarithmic lower bound for oblivious RAM (for all Parameters) ⋮ Upper and Lower Bounds for Dynamic Data Structures on Strings ⋮ Space efficient data structures for dynamic orthogonal range counting ⋮ Deterministic dynamic matching in worst-case update time ⋮ New amortized cell-probe lower bounds for dynamic problems ⋮ Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ Lower bound framework for differentially private and oblivious data structures ⋮ Lower bounds for (batch) PIR with private preprocessing ⋮ Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds ⋮ Semi-group range sum revisited: query-space lower bound tightened ⋮ Linear-space data structures for range mode query in arrays ⋮ A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs ⋮ Lower bounds for matrix factorization ⋮ Upper and Lower Bounds on the Power of Advice ⋮ Unnamed Item ⋮ Unnamed Item ⋮ 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: The cell probe complexity of dynamic range counting
