Approximate Trace Reconstruction via Median String (In Average-Case).

Diptarka Chakraborty Debarati Das Robert Krauthgamer

Published in: FSTTCS (2021)

Keyphrases

average case
worst case
uniform distribution
worst case analysis
learning curves
string matching
average case complexity
competitive ratio
edit distance
sample complexity
data sets
learning algorithm
multiresolution
upper bound