6 papers
Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck
William Kuszmaul, Jingxun Liang, Renfei Zhou
We show how to construct a dynamic ordered dictionary, supporting insert/delete/rank/select on a set of elements from a universe of size , that achieves the optimal amortize…
Static Retrieval Revisited: To Optimality and Beyond
Yang Hu, William Kuszmaul, Jingxun Liang +3
In the static retrieval problem, a data structure must answer retrieval queries mapping a set of keys in a universe to -bit values. Information-theoretically, retrieva…
Fingerprint Filters Are Optimal
William Kuszmaul, Jingxun Liang, Renfei Zhou
Dynamic filters are data structures supporting approximate membership queries to a dynamic set of keys, allowing a small false-positive error rate , under inse…
Optimal Static Fully Indexable Dictionaries
Jingxun Liang, Renfei Zhou
Fully indexable dictionaries (FID) store sets of integer keys while supporting rank/select queries. They serve as basic building blocks in many succinct data structures. Despite th…
Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
Josh Alman, Jingxun Liang
For an matrix , its rank- rigidity, denoted , is the minimum number of entries of that one must change to make its rank become at most .…
Optimal Static Dictionary with Worst-Case Constant Query Time
Yang Hu, Jingxun Liang, Huacheng Yu +2
In this paper, we design a new succinct static dictionary with worst-case constant query time. A dictionary data structure stores a set of key-value pairs with distinct keys in $[U…