32 citations · 63 across the 6 of their papers we have counts for
4 papers · 1 filter
(Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless
Vasileios Nakos, Zhao Song, Zhengyu Wang
In this paper, we consider the extensively studied problem of computing a -sparse approximation to the -dimensional Fourier transform of a length signal. Our algorithm us…
Parallel Graph Connectivity in Log Diameter Rounds
Alexandr Andoni, Clifford Stein, Zhao Song +2
We study graph connectivity problem in MPC model. On an undirected graph with nodes and edges, round connectivity algorithms have been known for over 35 years.…
BPTree: an heavy hitters algorithm using constant memory
Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin +3
The task of finding heavy hitters is one of the best known and well studied problems in the area of data streams. One is given a list and the goal is to…
An Improved Randomized Data Structure for Dynamic Graph Connectivity
Zhengyu Wang
We present a randomized algorithm for dynamic graph connectivity. With failure probability less than (for any constant we choose), our solution has worst case running t…