Bit-Probe Lower Bounds for Succinct Data Structures
From MaRDI portal
Publication:4910576
DOI10.1137/090766619zbMath1261.68049MaRDI QIDQ4910576
Publication date: 19 March 2013
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/bd39b557bbca4b47d06d6676450c68984e695e6b
lower bound; logarithmic forms; succinct data structure; membership; cell-probe; bit-probe; nonbinary array
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68P05: Data structures
Related Items
Nearly Optimal Static Las Vegas Succinct Dictionary, Sampling Lower Bounds: Boolean Average-Case and Permutations, On the bitprobe complexity of two probe adaptive schemes, Determining membership with 2 simultaneous queries, A Survey of Data Structures in the Bitprobe Model