1.9k citations · 2.8k across the 40 of their papers we have counts for
6 papers · 1 filter
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…
Extensions and Limitations of the Neural GPU
Eric Price, Wojciech Zaremba, Ilya Sutskever
The Neural GPU is a recent model that can learn algorithms such as multi-digit binary addition and binary multiplication in a way that generalizes to inputs of arbitrary length. We…
Equality of Opportunity in Supervised Learning
Moritz Hardt, Eric Price, Nathan Srebro
We propose a criterion for discrimination against a specified sensitive attribute in supervised learning, where the goal is to predict some target based on available features. Assu…
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…