
NearOptimal TwoPass Streaming Algorithm for Sampling Random Walks over Directed Graphs
For a directed graph G with n vertices and a start vertex u_ start, we w...
read it

Optimal bounds for approximate counting
Storing a counter incremented N times would naively consume O(log N) bit...
read it

MultiPass Graph Streaming Lower Bounds for Cycle Counting, MAXCUT, Matching Size, and Other Problems
Consider the following gap cycle counting problem in the streaming model...
read it

Tight Distributed Sketching Lower Bound for Connectivity
In this paper, we study the distributed sketching complexity of connecti...
read it

Succinct Filters for Sets of Unknown Sizes
The membership problem asks to maintain a set S⊆[u], supporting insertio...
read it

Lower Bound for Succinct Range Minimum Query
Given an integer array A[1..n], the Range Minimum Query problem (RMQ) as...
read it

Faster Update Time for Turnstile Streaming Algorithms
In this paper, we present a new algorithm for maintaining linear sketche...
read it

Nearly Optimal Static Las Vegas Succinct Dictionary
Given a set S of n (distinct) keys from key space [U], each associated w...
read it

How to Store a Random Walk
Motivated by storage applications, we study the following data structure...
read it

Optimal Succinct Rank Data Structure via Approximate Nonnegative Tensor Decomposition
Given an nbit array A, the succinct rank data structure problem asks to...
read it

Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation
We show optimal lower bounds for spanning forest computation in two diff...
read it

Distance Labelings on Random Power Law Graphs
A Distance Labeling scheme is a data structure that can answer shortest...
read it
Huacheng Yu
is this you? claim profile