Cell probe lower bounds for succinct data structures

MaRDI QIDQ4633874zbMATH OpenFDO

Authors Alexander Golynski

Publication date 6 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=1496839

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Nonnumerical algorithms (68W05)

Recommendations

• The cell probe complexity of succinct data structures
• Bit-probe lower bounds for succinct data structures
• Cell-probe lower bounds for succinct partial sums
• Bit-probe lower bounds for succinct data structures
• Logarithmic Lower Bounds in the Cell-Probe Model

Cited in

(12)

• The function-inversion problem: barriers and opportunities
• The cell probe complexity of succinct data structures
• Entropy-bounded representation of point grids
• Succinct representations of permutations and functions
• Efficient fully-compressed sequence representations
• On the cell probe complexity of membership and perfect hashing
• Sampling lower bounds: Boolean average-case and permutations
• Tight cell probe bounds for succinct Boolean matrix-vector multiplication
• Cell-probe lower bounds for the partial match problem
• Tighter lower bounds for nearest neighbor search and related problems in the cell probe model
• Succinct data structures for Baxter permutation and related families
• Strictly in-place algorithms for permuting and inverting permutations

This page was built for publication: Cell 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 Q4633874)