Publications (44)
Optimal Succinct Rank Data Structure via Approximate Nonnegative Tensor Decomposition
Huacheng Yu
Given an -bit array , the succinct rank data structure problem asks to construct a data structure using space bits for , supporting rank queries of form $\matht…
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…
Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
Cheng Jiang, Yinchen Liu, Huacheng Yu
A fundamental question in streaming complexity is whether every space-efficient turnstile algorithm is implicitly a linear sketch. The landmark work of Li, Nguyen, and Woodruff [LN…
Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries
Tianxiao Li, Jingxun Liang, Huacheng Yu +1
A dictionary data structure maintains a set of at most keys from the universe under key insertions and deletions, such that given a query , it returns if i…
A New Variation of Hat Guessing Games
Tengyu Ma, Xiaoming Sun, Huacheng Yu
Several variations of hat guessing games have been popularly discussed in recreational mathematics. In a typical hat guessing game, after initially coordinating a strategy, each of…
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…