5 citations · 7 across the 2 of their papers we have counts for
3 papers
cs.DS2019★ 2 cited
(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…
cs.DS2018
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.…
cs.CC2017★ 5 cited
Optimal lower bounds for universal relation, samplers, and finding duplicates
Jelani Nelson, Jakub Pachocki, Zhengyu Wang
In the communication problem (universal relation) [KRW95], Alice and Bob respectively receive and in with the promise that . The last pla…