1.9k citations · 2.8k across the 40 of their papers we have counts for
31 papers · 1 filter
A Simple Proof of a New Set Disjointness with Applications to Data Streams
Akshay Kamath, Eric Price, David P. Woodruff
The multiplayer promise set disjointness is one of the most widely used problems from communication complexity in applications. In this problem there are players with subsets $…
Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu
Arnab Bhattacharyya, Sutanu Gayen, Eric Price +1
We provide finite sample guarantees for the classical Chow-Liu algorithm (IEEE Trans.~Inform.~Theory, 1968) to learn a tree-structured graphical model of a distribution. For a dist…
Optimal Testing of Discrete Distributions with High Probability
Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane +2
We study the problem of testing discrete distributions with a focus on the high probability regime. Specifically, given samples from one or more discrete distributions, a property…
Lower Bounds for Compressed Sensing with Generative Models
Akshay Kamath, Sushrut Karmalkar, Eric Price
The goal of compressed sensing is to learn a structured signal from a limited number of noisy linear measurements . In traditional compressed sensing, "structure"…
Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering
Ilias Diakonikolas, Sushrut Karmalkar, Daniel Kane +2
We study high-dimensional sparse estimation tasks in a robust setting where a constant fraction of the dataset is adversarially corrupted. Specifically, we focus on the fundamental…
Separations and Equivalences between Turnstile Streaming and Linear Sketching
John Kallaugher, Eric Price
A longstanding observation, which was partially proven in \cite{LNW14,AHLW16}, is that any turnstile streaming algorithm can be implemented as a linear sketch (the reverse is trivi…