research
∙
11/07/2022
Approximate Trace Reconstruction from a Single Trace
The well-known trace reconstruction problem is the problem of inferring ...
share
research
∙
12/09/2021
Estimating the Longest Increasing Subsequence in Nearly Optimal Time
Longest Increasing Subsequence (LIS) is a fundamental statistic of a seq...
research
∙
07/24/2021
Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces
In the standard trace reconstruction problem, the goal is to exactly rec...
research
∙
12/04/2020
Polynomial-time trace reconstruction in the low deletion rate regime
In the trace reconstruction problem, an unknown source string x ∈{0,1}^n...
research
∙
08/27/2020
Polynomial-time trace reconstruction in the smoothed complexity model
In the trace reconstruction problem, an unknown source string x ∈{0,1}^n...
research
∙
07/12/2019
Efficient average-case population recovery in the presence of insertions and deletions
Several recent works have considered the trace reconstruction problem, i...
research
∙
04/11/2019
Beyond trace reconstruction: Population recovery from the deletion channel
Population recovery is the problem of learning an unknown distribution o...
research
∙
08/12/2018