8 citations · 21 across the 23 of their papers we have counts for
5 papers · 2 filters
Optimal bounds for approximate counting
Jelani Nelson, Huacheng Yu
Storing a counter incremented times would naively consume bits of memory. In 1978 Morris described the very first streaming algorithm: the "Morris Counter". His alg…
Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems
Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena +1
Consider the following gap cycle counting problem in the streaming model: The edges of a -regular -vertex graph are arriving one-by-one in a stream and we are promised th…
Tight Distributed Sketching Lower Bound for Connectivity
Huacheng Yu
In this paper, we study the distributed sketching complexity of connectivity. In distributed graph sketching, an -node graph is distributed to players such that each pla…
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…