4 citations · 8 across the 5 of their papers we have counts for
5 papers
Cell-Probe Lower Bound for Accessible Interval Graphs
Sankardeep Chakraborty, Christian Engels, Seungbum Jo +1
We spot a hole in the area of succinct data structures for graph classes from a universe of size at most . Very often, the input graph is labeled by the user in an arbitrary a…
Nearly Tight Lower Bound for Range Minimum Query via Probe-by-Probe Information Accounting
Mingmou Liu
We prove a nearly tight lower bound for succinct Range Minimum Query (RMQ) on an array of distinct integers. A query returns the position of the smallest entry in a specified s…
Succinct Filters for Sets of Unknown Sizes
Mingmou Liu, Yitong Yin, Huacheng Yu
The membership problem asks to maintain a set , supporting insertions and membership queries, i.e., testing if a given element is in the set. A data structure that c…
Lower Bound for Succinct Range Minimum Query
Mingmou Liu, Huacheng Yu
Given an integer array , the Range Minimum Query problem (RMQ) asks to preprocess into a data structure, supporting RMQ queries: given , return the index…
Randomized approximate nearest neighbor search with limited adaptivity
Mingmou Liu, Xiaoyin Pan, Yitong Yin
We study the fundamental problem of approximate nearest neighbor search in -dimensional Hamming space . We study the complexity of the problem in the famous cell-prob…