Logarithmic Lower Bounds in the Cell-Probe Model

DOI10.1137/S0097539705447256zbMath1122.68044OpenAlexW1963524245WikidataQ60638762 ScholiaQ60638762MaRDI QIDQ5470720

Erik D. Demaine, Mihai Pǎtraşcu

Publication date: 1 June 2006

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539705447256

zbMATH Keywords

data structureslower boundscell-probe complexitydynamic graph problemspartial-sums problem

Mathematics Subject Classification ID

Related Items (38)

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Upper and lower bounds for fully retroactive graph problems ⋮ On dynamic bit-probe complexity ⋮ A logarithmic lower bound for oblivious RAM (for all Parameters) ⋮ A deterministic \(O(m \log {m})\) time algorithm for the Reeb graph ⋮ Stronger lower bounds for online ORAM ⋮ New amortized cell-probe lower bounds for dynamic problems ⋮ Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ Optimal decremental connectivity in planar graphs ⋮ Dynamic planar embeddings of dynamic graphs ⋮ Lower bound framework for differentially private and oblivious data structures ⋮ Random access in persistent strings and segment selection ⋮ Limits of breach-resistant and snapshot-oblivious RAMs ⋮ Deterministic Fault-Tolerant Connectivity Labeling Scheme ⋮ Trade-offs in dynamic coloring for bipartite and general graphs ⋮ Unnamed Item ⋮ Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds ⋮ Succinct Partial Sums and Fenwick Trees ⋮ Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model ⋮ A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs ⋮ Is there an oblivious RAM lower bound for online reads? ⋮ Succinct data structures for searchable partial sums with optimal worst-case performance ⋮ Is there an oblivious RAM lower bound for online reads? ⋮ Fully Functional Static and Dynamic Succinct Trees ⋮ Rank/select on dynamic compressed sequences and applications ⋮ Dynamic path queries in linear space ⋮ Lower bounds for matrix factorization ⋮ Partial sums on the ultra-wide word RAM ⋮ Fully dynamic arboricity maintenance ⋮ Constant-time dynamic weight approximation for minimum spanning forest ⋮ Dynamic connectivity for axis-parallel rectangles ⋮ Upper and Lower Bounds on the Power of Advice ⋮ Unnamed Item ⋮ Distance-Preserving Subgraphs of Interval Graphs ⋮ Lower bounds for matrix factorization ⋮ Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones ⋮ Lower bounds for encrypted multi-maps and searchable encryption in the leakage cell probe model ⋮ Unnamed Item

This page was built for publication: Logarithmic Lower Bounds in the Cell-Probe Model