Bit-Probe Lower Bounds for Succinct Data Structures

DOI10.1137/090766619zbMath1261.68049OpenAlexW1998068971MaRDI QIDQ4910576

Emanuele Viola

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

zbMATH Keywords

lower boundlogarithmic formssuccinct data structuremembershipcell-probebit-probenonbinary array

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (5)

On the bitprobe complexity of two probe adaptive schemes ⋮ Nearly Optimal Static Las Vegas Succinct Dictionary ⋮ Determining membership with 2 simultaneous queries ⋮ Sampling Lower Bounds: Boolean Average-Case and Permutations ⋮ A Survey of Data Structures in the Bitprobe Model

This page was built for publication: Bit-Probe Lower Bounds for Succinct Data Structures