32 citations · 63 across the 6 of their papers we have counts for
7 papers
(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.…
Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams
Michael Kapralov, Jelani Nelson, Jakub Pachocki +3
In the communication problem (universal relation) [KRW95], Alice and Bob respectively receive with the promise that . The last player to…
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…
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…
Characterizing Propositional Proofs as Non-Commutative Formulas
Fu Li, Iddo Tzameret, Zhengyu Wang
Does every Boolean tautology have a short propositional-calculus proof? Here, a propositional calculus (i.e. Frege) proof is a proof starting from a set of axioms and deriving new…