  Trace reconstruction is the problem of learning an unknown string $x$ from
independent traces of $x$, where traces are generated by independently deleting
each bit of $x$ with some deletion probability $q$. In this paper, we initiate
the study of Circular trace reconstruction, where the unknown string $x$ is
circular and traces are now rotated by a random cyclic shift. Trace
reconstruction is related to many computational biology problems studying DNA,
which is a primary motivation for this problem as well, as many types of DNA
are known to be circular.
  Our main results are as follows. First, we prove that we can reconstruct
arbitrary circular strings of length $n$ using
$\exp\big(\tilde{O}(n^{1/3})\big)$ traces for any constant deletion probability
$q$, as long as $n$ is prime or the product of two primes. For $n$ of this
form, this nearly matches what was the best known bound of
$\exp\big(O(n^{1/3})\big)$ for standard trace reconstruction when this paper
was initially released. We note, however, that Chase very recently improved the
standard trace reconstruction bound to $\exp\big(\tilde{O}(n^{1/5})\big)$.
Next, we prove that we can reconstruct random circular strings with high
probability using $n^{O(1)}$ traces for any constant deletion probability $q$.
Finally, we prove a lower bound of $\tilde{\Omega}(n^3)$ traces for arbitrary
circular strings, which is greater than the best known lower bound of
$\tilde{\Omega}(n^{3/2})$ in standard trace reconstruction.
