72 citations · 399 across the 60 of their papers we have counts for
16 papers · 1 filter
Testing Convex Truncation
Anindya De, Shivam Nadimpalli, Rocco A. Servedio
We study the basic statistical problem of testing whether normally distributed -dimensional data has been truncated, i.e. altered by only retaining points that lie in some unkno…
Approximate Trace Reconstruction from a Single Trace
Xi Chen, Anindya De, Chin Ho Lee +2
The well-known trace reconstruction problem is the problem of inferring an unknown source string from independent "traces", i.e. copies of that have been corr…
Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces
Xi Chen, Anindya De, Chin Ho Lee +2
In the standard trace reconstruction problem, the goal is to \emph{exactly} reconstruct an unknown source string from independent "traces", which are cop…
Approximating Sumset Size
Anindya De, Shivam Nadimpalli, Rocco A. Servedio
Given a subset of the -dimensional Boolean hypercube , the sumset is the set where addition is in . Sumsets pla…
Polynomial-time trace reconstruction in the low deletion rate regime
Xi Chen, Anindya De, Chin Ho Lee +2
In the \emph{trace reconstruction problem}, an unknown source string is transmitted through a probabilistic \emph{deletion channel} which independently deletes ea…
Polynomial-time trace reconstruction in the smoothed complexity model
Xi Chen, Anindya De, Chin Ho Lee +2
In the \emph{trace reconstruction problem}, an unknown source string is sent through a probabilistic \emph{deletion channel} which independently deletes each bit…
A Lower Bound on Cycle-Finding in Sparse Digraphs
Xi Chen, Tim Randolph, Rocco A. Servedio +1
We consider the problem of finding a cycle in a sparse directed graph that is promised to be far from acyclic, meaning that the smallest feedback arc set in is large. We pr…
Efficient average-case population recovery in the presence of insertions and deletions
Frank Ban, Xi Chen, Rocco A. Servedio +1
Several recent works have considered the \emph{trace reconstruction problem}, in which an unknown source string is transmitted through a probabilistic channel which…
Learning from satisfying assignments under continuous distributions
Clément L. Canonne, Anindya De, Rocco A. Servedio
What kinds of functions are learnable from their satisfying assignments? Motivated by this simple question, we extend the framework of De, Diakonikolas, and Servedio [DDS15], which…
Beyond trace reconstruction: Population recovery from the deletion channel
Frank Ban, Xi Chen, Adam Freilich +2
\emph{Population recovery} is the problem of learning an unknown distribution over an unknown set of -bit strings, given access to independent draws from the distribution that h…
Learning Sums of Independent Random Variables with Sparse Collective Support
Anindya De, Philip M. Long, Rocco A. Servedio
We study the learnability of sums of independent integer random variables given a bound on the size of the union of their supports. For , a sum…
Sharp bounds for population recovery
Anindya De, Ryan O'Donnell, Rocco Servedio
The population recovery problem is a basic problem in noisy unsupervised learning that has attracted significant research attention in recent years [WY12,DRWY12, MS13, BIMP13, LZ15…
A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage
Constantinos Daskalakis, Anindya De, Ilias Diakonikolas +2
We consider a problem which has received considerable attention in systems literature because of its applications to routing in delay tolerant networks and replica placement in dis…
Testing probability distributions using conditional samples
Clement Canonne, Dana Ron, Rocco A. Servedio
We study a new framework for property testing of probability distributions, by considering distribution testing algorithms that have access to a conditional sampling oracle.* This…
Testing -Modal Distributions: Optimal Algorithms via Reductions
Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio +2
We give highly efficient algorithms, and almost matching lower bounds, for a range of basic statistical problems that involve testing and estimating the L_1 distance between two k-…
Learning Poisson Binomial Distributions
Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio
We consider a basic problem in unsupervised learning: learning an unknown \emph{Poisson Binomial Distribution}. A Poisson Binomial Distribution (PBD) over is the…