4 citations · 6 across the 6 of their papers we have counts for
13 papers
Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs
Lijie Chen, Gillat Kol, Dmitry Paramonov +3
For a directed graph with vertices and a start vertex , we wish to (approximately) sample an -step random walk over starting from with…
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…
Faster Update Time for Turnstile Streaming Algorithms
Josh Alman, Huacheng Yu
In this paper, we present a new algorithm for maintaining linear sketches in turnstile streams with faster update time. As an application, we show that \texttt{Count} sket…
Nearly Optimal Static Las Vegas Succinct Dictionary
Huacheng Yu
Given a set of (distinct) keys from key space , each associated with a value from , the \emph{static dictionary} problem asks to preprocess these (key, value) pairs…