The cell probe complexity of succinct data structures
From MaRDI portal
Publication:2373728
Recommendations
Cites work
- scientific article; zbMATH DE number 3577144 (Why is no real title available?)
- scientific article; zbMATH DE number 1261820 (Why is no real title available?)
- scientific article; zbMATH DE number 512871 (Why is no real title available?)
- scientific article; zbMATH DE number 1052006 (Why is no real title available?)
- scientific article; zbMATH DE number 2038721 (Why is no real title available?)
- scientific article; zbMATH DE number 2079421 (Why is no real title available?)
- scientific article; zbMATH DE number 1830754 (Why is no real title available?)
- scientific article; zbMATH DE number 1875423 (Why is no real title available?)
- scientific article; zbMATH DE number 3314813 (Why is no real title available?)
- A linear lower bound on index size for text retrieval
- A lower bound for finding predecessors in Yao's cell probe model
- A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube
- A parallel search game
- Are bitvectors optimal?
- Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
- Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
- Families of \(k\)-independent sets
- Intersection Theorems for Systems of Sets
- List decoding from erasures: bounds and code constructions
- Low redundancy in static dictionaries with constant query time
- Membership in Constant Time and Almost-Minimum Space
- On data structures and asymmetric communication complexity
- On the cell probe complexity of polynomial evaluation
- Optimal bounds for the predecessor problem and related problems
- Products and Help Bits in Decision Trees
- Simple Constructions of Almost k-wise Independent Random Variables
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- The Complexity of Some Simple Retrieval Problems
- Tighter lower bounds for nearest neighbor search and related problems in the cell probe model
- Vector sets for exhaustive testing of logic circuits
Cited in
(33)- Optimal succinct rank data structure via approximate nonnegative tensor decomposition
- Optimal indexes for sparse bit vectors
- Succinct representations of permutations and functions
- Lower bounds for matrix factorization
- Bounded-depth circuits cannot sample good codes
- Bit-probe lower bounds for succinct data structures
- LRM-trees: compressed indices, adaptive sorting, and compressed permutations
- A Survey of Data Structures in the Bitprobe Model
- Bit-probe lower bounds for succinct data structures
- Efficiency of linked cell algorithms
- On partial information retrieval: the unconstrained 100 prisoner problem
- LRM-trees: compressed indices, adaptive sorting, and compressed permutations
- Cell-probe lower bounds for succinct partial sums
- Cell probe lower bounds for succinct data structures
- On the cell probe complexity of membership and perfect hashing
- On space efficient two dimensional range minimum data structures
- Succinct representations of ordinal trees
- Sampling lower bounds: Boolean average-case and permutations
- scientific article; zbMATH DE number 7250167 (Why is no real title available?)
- Random access to high-order entropy compressed text
- Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity
- Lower bounds for data structures with space close to maximum imply circuit lower bounds
- On the Redundancy of Succinct Data Structures
- Coding for Sunflowers
- The function-inversion problem: barriers and opportunities
- Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
- Algorithms and Computation
- Computing (and Life) Is All about Tradeoffs
- Query time versus redundancy trade-offs for range queries
- The cycle structure of a Markoff automorphism over finite fields
- Tight cell probe bounds for succinct Boolean matrix-vector multiplication
- Sunflowers: from soil to oil
- On the cell probe complexity of polynomial evaluation
This page was built for publication: The cell probe complexity of succinct data structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2373728)
