72 citations · 262 across the 30 of their papers we have counts for
6 papers · 1 filter
Testing noisy linear functions for sparsity
Xue Chen, Anindya De, Rocco A. Servedio
We consider the following basic inference problem: there is an unknown high-dimensional vector , and an algorithm is given access to labeled pairs where…
Kruskal-Katona for convex sets, with applications
Anindya De, Rocco A. Servedio
The well-known Kruskal-Katona theorem in combinatorics says that (under mild conditions) every monotone Boolean function has a nontrivial "density increm…
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…