Logarithmic Lower Bounds in the Cell-Probe Model
From MaRDI portal
Publication:5470720
DOI10.1137/S0097539705447256zbMath1122.68044WikidataQ60638762 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
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68P05: Data structures
Related Items
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture, Unnamed Item, Lower bounds for matrix factorization, Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds, Succinct Partial Sums and Fenwick Trees, Distance-Preserving Subgraphs of Interval Graphs, Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones, Unnamed Item, Is there an oblivious RAM lower bound for online reads?, Is there an oblivious RAM lower bound for online reads?, Partial sums on the ultra-wide word RAM, Fully dynamic arboricity maintenance, Unnamed Item, Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover, 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, Succinct data structures for searchable partial sums with optimal worst-case performance, Rank/select on dynamic compressed sequences and applications, Upper and lower bounds for fully retroactive graph problems, Dynamic connectivity for axis-parallel rectangles, Optimal decremental connectivity in planar graphs, Dynamic planar embeddings of dynamic graphs, Dynamic path queries in linear space, A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs, Lower bounds for matrix factorization, Constant-time dynamic weight approximation for minimum spanning forest, Lower bounds for encrypted multi-maps and searchable encryption in the leakage cell probe model, A logarithmic lower bound for oblivious RAM (for all Parameters), Stronger lower bounds for online ORAM, On dynamic bit-probe complexity, A deterministic \(O(m \log {m})\) time algorithm for the Reeb graph, New amortized cell-probe lower bounds for dynamic problems, Trade-offs in dynamic coloring for bipartite and general graphs, Fully Functional Static and Dynamic Succinct Trees, Upper and Lower Bounds on the Power of Advice, Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model
