1.9k citations · 2.8k across the 40 of their papers we have counts for
4 papers · 2 filters
Collision-based Testers are Optimal for Uniformity and Closeness
Ilias Diakonikolas, Themis Gouleakis, John Peebles +1
We study the fundamental problems of (i) uniformity testing of a discrete distribution, and (ii) closeness testing between two discrete distributions with bounded -norm. Th…
A Hybrid Sampling Scheme for Triangle Counting
John Kallaugher, Eric Price
We study the problem of estimating the number of triangles in a graph stream. No streaming algorithm can get sublinear space on all graphs, so methods in this area bound the space…
Fourier-sparse interpolation without a frequency gap
Xue Chen, Daniel M. Kane, Eric Price +1
We consider the problem of estimating a Fourier-sparse signal from noisy samples, where the sampling is done over some interval and the frequencies can be "off-grid". Prev…
A Robust Sparse Fourier Transform in the Continuous Setting
Eric Price, Zhao Song
In recent years, a number of works have studied methods for computing the Fourier transform in sublinear time if the output is sparse. Most of these have focused on the discrete se…