In the trace reconstruction problem, an unknown source string $x \in \{0,1\}^n$ is transmitted through a probabilistic deletion channel which independently deletes each bit with some fixed probability $\delta$ and concatenates the surviving bits, resulting in a trace of $x$. The problem is to reconstruct $x$ given access to independent traces.
Trace reconstruction of arbitrary (worst-case) strings is a challenging problem, with the current state of the art for $\poly(n)$-time algorithms being the 2004 algorithm of Batu et al.~\cite{BKKM04}. This algorithm can reconstruct an arbitrary source string $x \in \{0,1\}^n$ in $\poly(n)$ time provided that the deletion rate $\delta$ satisfies $\delta \leq n^{-(1/2 + \varepsilon)}$ for some $\varepsilon > 0$.
In this work we improve on the result of \cite{BKKM04} by giving a $\poly(n)$-time algorithm for trace reconstruction for any deletion rate $\delta \leq n^{-(1/3 + \varepsilon)}$. Our algorithm works by alternating an alignment-based procedure, which we show effectively reconstructs portions of the source string that are not ``highly repetitive'', with a novel procedure that efficiently determines the length of highly repetitive subwords of the source string.