97 citations · 543 across the 40 of their papers we have counts for
6 papers · 1 filter
A Chasm Between Identity and Equivalence Testing with Conditional Queries
Jayadev Acharya, Clément L. Canonne, Gautam Kamath
A recent model for property testing of probability distributions (Chakraborty et al., ITCS 2013, Canonne et al., SICOMP 2015) enables tremendous savings in the sample complexity of…
Testing Poisson Binomial Distributions
Jayadev Acharya, Constantinos Daskalakis
A Poisson Binomial distribution over variables is the distribution of the sum of independent Bernoullis. We provide a sample near-optimal algorithm for testing whether a di…
Estimating Renyi Entropy of Discrete Distributions
Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh +1
It was recently shown that estimating the Shannon entropy of a discrete -symbol distribution requires samples, a number that grows near-line…
Universal Compression of Envelope Classes: Tight Characterization via Poisson Sampling
Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky +1
The Poisson-sampling technique eliminates dependencies among symbol appearances in a random sequence. It has been used to simplify the analysis and strengthen the performance guara…
String Reconstruction from Substring Compositions
Jayadev Acharya, Hirakendu Das, Olgica Milenkovic +2
Motivated by mass-spectrometry protein sequencing, we consider a simply-stated problem of reconstructing a string from the multiset of its substring compositions. We show that all…
Near-optimal-sample estimators for spherical Gaussian mixtures
Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky +1
Statistical and machine-learning algorithms are frequently applied to high-dimensional data. In many of these applications data is scarce, and often much more costly than computati…