Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

DOI10.1137/18M1198429zbMath1494.68073OpenAlexW3012468277MaRDI QIDQ5130847

Huacheng Yu, Kasper Green Larsen, Omri Weinstein

Publication date: 29 October 2020

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/18m1198429

zbMATH Keywords

lower boundsrange searchingdynamic problemsdata structurecell-probe complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Communication complexity, information complexity (68Q11)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Towards optimal range medians
• On the cell probe complexity of polynomial evaluation
• The cell probe complexity of succinct data structures
• Cell-Probe Proofs
• Decomposable searching problems I. Static-to-dynamic transformation
• Should Tables Be Sorted?
• The cell probe complexity of dynamic range counting
• Logarithmic Lower Bounds in the Cell-Probe Model
• Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting

This page was built for publication: Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds