R. Servedio

activity

20002022

most citedImproved Bounds on Quantum Learning Algorithms

72 citations · 262 across the 29 of their papers we have counts for

collaborators

Showing cs.DSShow all

11 papers · 1 filter

cs.DS2022

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 $x \in {0, 1}^{n}$ from independent "traces", i.e. copies of $x$ that have been corr…

cs.DS2021

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 $x \in {0, 1}^{n}$ from independent "traces", which are cop…

cs.DS2021

Approximating Sumset Size

Anindya De, Shivam Nadimpalli, Rocco A. Servedio

Given a subset $A$ of the $n$ -dimensional Boolean hypercube $F_{2}^{n}$ , the sumset $A + A$ is the set ${a + a^{'} : a, a^{'} \in A}$ where addition is in $F_{2}^{n}$ . Sumsets pla…

cs.DS2020

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 $x \in {0, 1}^{n}$ is transmitted through a probabilistic \emph{deletion channel} which independently deletes ea…

cs.DS2020★ 2 cited

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 $x \in {0, 1}^{n}$ is sent through a probabilistic \emph{deletion channel} which independently deletes each bit…

cs.DS2019

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 $G$ that is promised to be far from acyclic, meaning that the smallest feedback arc set in $G$ is large. We pr…