72 citations · 399 across the 60 of their papers we have counts for
4 papers · 2 filters
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…