Logarithmic Lower Bounds in the Cell-Probe Model
From MaRDI portal
Recommendations
Cited in
(67)- Dynamic connectivity for axis-parallel rectangles
- On estimating the complexity of logarithmic decomposition
- Lower bounds for dynamic data structures on algebraic RAMs
- Optimal decremental connectivity in planar graphs
- Dynamic planar embeddings of dynamic graphs
- Dynamic path queries in linear space
- Logarithmic lower bounds for Néel walls
- 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
- The limits of buffering: a tight lower bound for dynamic membership in the external memory model
- The limits of buffering: a tight lower bound for dynamic membership in the external memory model
- Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model
- Unifying the landscape of cell-probe lower bounds
- scientific article; zbMATH DE number 1002202 (Why is no real title available?)
- Lower bounds for dynamic connectivity
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Cell probe lower bounds for succinct data structures
- New Lower Bound Techniques for Dynamic Partial Sums and Related Problems
- Lower bounds for matrix factorization
- Distance-preserving subgraphs of interval graphs
- Nearly optimal separation between partially and fully retroactive data structures
- scientific article; zbMATH DE number 7250167 (Why is no real title available?)
- Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
- Succinct partial sums and Fenwick trees
- Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds
- Cell-probe lower bounds from online communication complexity
- Cell-probe lower bounds for dynamic problems via a new communication model
- The cell probe complexity of dynamic range counting
- On the cell probe complexity of dynamic membership
- Tight bounds for the partial-sums problem
- Steiner shallow-light trees are exponentially lighter than spanning ones
- A little advice can be very helpful
- 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
- A generalization of a lower bound technique due to Fredman and Saks
- scientific article; zbMATH DE number 7765406 (Why is no real title available?)
- 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
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- Good \(r\)-divisions imply optimal amortized decremental biconnectivity
- Lower bounds for semi-adaptive data structures via corruption
- Dynamic longest common substring in polylogarithmic time
- (Worst-case) optimal adaptive dynamic bitvectors
- Memory checking requires logarithmic overhead
- A logarithmic lower bound for oblivious RAM (for all parameters)
- Deterministic fault-tolerant connectivity labeling scheme
- Almost optimal exact distance oracles for planar graphs
- Succinct data structures for searchable partial sums with optimal worst-case performance
- Good r-divisions imply optimal amortized decremental biconnectivity
- Time/space tradeoffs for generic attacks on delay functions
- Rank/select on dynamic compressed sequences and applications
- Upper and lower bounds for fully retroactive graph problems
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)
