Bit-probe lower bounds for succinct data structures

DOI10.1137/090766619MaRDI QIDQ4910576zbMATH OpenOpenAlexFDO

Authors 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

bit-probecell-probelogarithmic formslower boundmembershipnonbinary arraysuccinct data structure

Mathematics Subject Classification ID

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

Recommendations

• Bit-probe lower bounds for succinct data structures
• Set membership with a few bit probes
• Data structures for storing small sets in the bitprobe model
• The cell probe complexity of succinct data structures
• Set membership with non-adaptive bit probes

Cited in

(15)

• On the bitprobe complexity of two probe adaptive schemes
• Determining membership with 2 simultaneous queries
• The cell probe complexity of succinct data structures
• A Survey of Data Structures in the Bitprobe Model
• On the Redundancy of Succinct Data Structures
• scientific article; zbMATH DE number 3974286 (Why is no real title available?)
• Cell probe lower bounds for succinct data structures
• scientific article; zbMATH DE number 1875423 (Why is no real title available?)
• Nearly Optimal Static Las Vegas Succinct Dictionary
• Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
• Bit-probe lower bounds for succinct data structures
• Sampling lower bounds: Boolean average-case and permutations
• Cell-probe lower bounds for succinct partial sums
• Automata, Languages and Programming
• Data Structures Lower Bounds and Popular Conjectures

This page was built for publication: Bit-probe lower bounds for succinct data structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4910576)