The cell probe complexity of succinct data structures
From MaRDI portal
Publication:2373728
DOI10.1016/J.TCS.2007.02.047zbMATH Open1152.68428OpenAlexW2101403145MaRDI QIDQ2373728FDOQ2373728
Authors: Anna Gál, Peter Bro Miltersen 
Publication date: 16 July 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2006/606/
Recommendations
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Families of \(k\)-independent sets
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Simple Constructions of Almost k-wise Independent Random Variables
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Intersection Theorems for Systems of Sets
- List decoding from erasures: bounds and code constructions
- A lower bound for finding predecessors in Yao's cell probe model
- Title not available (Why is that?)
- Optimal bounds for the predecessor problem and related problems
- On data structures and asymmetric communication complexity
- Products and Help Bits in Decision Trees
- Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
- Low redundancy in static dictionaries with constant query time
- Membership in Constant Time and Almost-Minimum Space
- Title not available (Why is that?)
- Vector sets for exhaustive testing of logic circuits
- Title not available (Why is that?)
- Are bitvectors optimal?
- Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
- On the cell probe complexity of polynomial evaluation
- A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube
- Tighter lower bounds for nearest neighbor search and related problems in the cell probe model
- A parallel search game
- The Complexity of Some Simple Retrieval Problems
- Title not available (Why is that?)
- A linear lower bound on index size for text retrieval
Cited In (33)
- Optimal indexes for sparse bit vectors
- Succinct representations of permutations and functions
- Lower bounds for matrix factorization
- Bit-probe lower bounds for succinct data structures
- Bounded-depth circuits cannot sample good codes
- LRM-trees: compressed indices, adaptive sorting, and compressed permutations
- Bit-probe lower bounds for succinct data structures
- A Survey of Data Structures in the Bitprobe Model
- 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
- Succinct representations of ordinal trees
- On space efficient two dimensional range minimum data structures
- Sampling lower bounds: Boolean average-case and permutations
- Title not available (Why is that?)
- 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
- Coding for Sunflowers
- On the Redundancy of Succinct Data Structures
- 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
- Tight cell probe bounds for succinct Boolean matrix-vector multiplication
- The cycle structure of a Markoff automorphism over finite fields
- Sunflowers: from soil to oil
- Optimal succinct rank data structure via approximate nonnegative tensor decomposition
- 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)
