Logarithmic Lower Bounds in the Cell-Probe Model
From MaRDI portal
Publication:5470720
Recommendations
Cited in
(57)- Random access in persistent strings and segment selection
- Stronger lower bounds for online ORAM
- The cell probe complexity of dynamic range counting
- Succinct partial sums and Fenwick trees
- Steiner shallow-light trees are exponentially lighter than spanning ones
- Upper and lower bounds for fully retroactive graph problems
- Lower bound framework for differentially private and oblivious data structures
- Lower bounds for matrix factorization
- Lower bounds for matrix factorization
- Dynamic connectivity for axis-parallel rectangles
- A generalization of a lower bound technique due to Fredman and Saks
- Is there an oblivious RAM lower bound for online reads?
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds
- Succinct data structures for searchable partial sums with optimal worst-case performance
- Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- 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
- Logarithmic lower bounds for Néel walls
- On estimating the complexity of logarithmic decomposition
- Nearly optimal separation between partially and fully retroactive data structures
- Cell probe lower bounds for succinct data structures
- A logarithmic lower bound for oblivious RAM (for all Parameters)
- Distance-preserving subgraphs of interval graphs
- Rank/select on dynamic compressed sequences and applications
- Is there an oblivious RAM lower bound for online reads?
- The limits of buffering: a tight lower bound for dynamic membership in the external memory model
- On dynamic bit-probe complexity
- Cell-probe lower bounds for dynamic problems via a new communication model
- Good \(r\)-divisions imply optimal amortized decremental biconnectivity
- The limits of buffering: a tight lower bound for dynamic membership in the external memory model
- scientific article; zbMATH DE number 7250167 (Why is no real title available?)
- 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
- Constant-time dynamic weight approximation for minimum spanning forest
- Partial sums on the ultra-wide word RAM
- Dynamic path queries in linear space
- A little advice can be very helpful
- Fully functional static and dynamic succinct trees
- Deterministic Fault-Tolerant Connectivity Labeling Scheme
- A deterministic \(O(m \log {m})\) time algorithm for the Reeb graph
- Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
- scientific article; zbMATH DE number 7765406 (Why is no real title available?)
- Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model
- Optimal decremental connectivity in planar graphs
- Fully dynamic arboricity maintenance
- Trade-offs in dynamic coloring for bipartite and general graphs
- Dynamic planar embeddings of dynamic graphs
- Lower bounds for dynamic connectivity
- Tight bounds for the partial-sums problem
- New amortized cell-probe lower bounds for dynamic problems
- On the cell probe complexity of dynamic membership
- Unifying the landscape of cell-probe lower bounds
- Lower bounds for encrypted multi-maps and searchable encryption in the leakage cell probe model
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)
