Logarithmic Lower Bounds in the Cell-Probe Model
From MaRDI portal
Publication:5470720
DOI10.1137/S0097539705447256zbMATH Open1122.68044DBLPjournals/siamcomp/PatrascuD06OpenAlexW1963524245WikidataQ60638762 ScholiaQ60638762MaRDI QIDQ5470720FDOQ5470720
Authors: Mihai Patrascu, Erik D. Demaine 
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
Recommendations
Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (57)
- Good \(r\)-divisions imply optimal amortized decremental biconnectivity
- The cell probe complexity of dynamic range counting
- Succinct partial sums and Fenwick trees
- Steiner shallow-light trees are exponentially lighter than spanning ones
- Lower bound framework for differentially private and oblivious data structures
- Upper and lower bounds for fully retroactive graph problems
- Lower bounds for matrix factorization
- A generalization of a lower bound technique due to Fredman and Saks
- Lower bounds for matrix factorization
- Is there an oblivious RAM lower bound for online reads?
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- Dynamic connectivity for axis-parallel rectangles
- Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds
- Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Succinct data structures for searchable partial sums with optimal worst-case performance
- Cell-probe lower bounds from online communication complexity
- New Lower Bound Techniques for Dynamic Partial Sums and Related Problems
- A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs
- Nearly optimal separation between partially and fully retroactive data structures
- Logarithmic lower bounds for Néel walls
- Cell probe lower bounds for succinct data structures
- On estimating the complexity of logarithmic decomposition
- Distance-preserving subgraphs of interval graphs
- A logarithmic lower bound for oblivious RAM (for all Parameters)
- Is there an oblivious RAM lower bound for online reads?
- Rank/select on dynamic compressed sequences and applications
- The limits of buffering: a tight lower bound for dynamic membership in the external memory model
- Cell-probe lower bounds for dynamic problems via a new communication model
- On dynamic bit-probe complexity
- Title not available (Why is that?)
- The limits of buffering: a tight lower bound for dynamic membership in the external memory model
- Limits of breach-resistant and snapshot-oblivious RAMs
- Upper and lower bounds on the power of advice
- Lower bounds for dynamic data structures on algebraic RAMs
- Partial sums on the ultra-wide word RAM
- A little advice can be very helpful
- Constant-time dynamic weight approximation for minimum spanning forest
- Deterministic Fault-Tolerant Connectivity Labeling Scheme
- Fully functional static and dynamic succinct trees
- Dynamic path queries in linear space
- A deterministic \(O(m \log {m})\) time algorithm for the Reeb graph
- Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
- Title not available (Why is that?)
- Fully dynamic arboricity maintenance
- Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model
- Optimal decremental connectivity in planar graphs
- Trade-offs in dynamic coloring for bipartite and general graphs
- Dynamic planar embeddings of dynamic graphs
- Tight bounds for the partial-sums problem
- Lower bounds for dynamic connectivity
- On the cell probe complexity of dynamic membership
- New amortized cell-probe lower bounds for dynamic problems
- Unifying the landscape of cell-probe lower bounds
- Random access in persistent strings and segment selection
- Lower bounds for encrypted multi-maps and searchable encryption in the leakage cell probe model
- Stronger lower bounds for online ORAM
This page was built for publication: Logarithmic Lower Bounds in the Cell-Probe Model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5470720)
