The cell probe complexity of succinct data structures

DOI10.1016/j.tcs.2007.02.047zbMath1152.68428OpenAlexW2101403145MaRDI QIDQ2373728

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/

zbMATH Keywords

succinct data structurescell probe complexitypolynomial evaluation with preprocessing

Mathematics Subject Classification ID

Data structures (68P05)

Related Items (19)

Sunflowers: from soil to oil ⋮ The function-inversion problem: barriers and opportunities ⋮ On partial information retrieval: the unconstrained 100 prisoner problem ⋮ Succinct representations of permutations and functions ⋮ Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds ⋮ Optimal indexes for sparse bit vectors ⋮ LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations ⋮ LRM-trees: compressed indices, adaptive sorting, and compressed permutations ⋮ On space efficient two dimensional range minimum data structures ⋮ Bounded-depth circuits cannot sample good codes ⋮ Coding for Sunflowers ⋮ Sampling Lower Bounds: Boolean Average-Case and Permutations ⋮ Unnamed Item ⋮ The cycle structure of a Markoff automorphism over finite fields ⋮ Lower bounds for matrix factorization ⋮ Computing (and Life) Is All about Tradeoffs ⋮ Random Access to High-Order Entropy Compressed Text ⋮ A Survey of Data Structures in the Bitprobe Model ⋮ Succinct Representations of Ordinal Trees

Cites Work

• On the cell probe complexity of polynomial evaluation
• Tighter lower bounds for nearest neighbor search and related problems in the cell probe model
• A lower bound for finding predecessors in Yao's cell probe model
• On data structures and asymmetric communication complexity
• Optimal bounds for the predecessor problem and related problems
• Families of \(k\)-independent sets
• Low Redundancy in Static Dictionaries with Constant Query Time
• A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
• Are bitvectors optimal?
• Intersection Theorems for Systems of Sets
• List decoding from erasures: bounds and code constructions
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Vector sets for exhaustive testing of logic circuits
• Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
• Simple Constructions of Almost k-wise Independent Random Variables
• The Complexity of Some Simple Retrieval Problems
• Products and Help Bits in Decision Trees
• Membership in Constant Time and Almost-Minimum Space
• A linear lower bound on index size for text retrieval
• A parallel search game
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The cell probe complexity of succinct data structures