  The goal of trace reconstruction is to reconstruct an unknown $n$-bit string
$x$ given only independent random traces of $x$, where a random trace of $x$ is
obtained by passing $x$ through a deletion channel. A Statistical Query (SQ)
algorithm for trace reconstruction is an algorithm which can only access
statistical information about the distribution of random traces of $x$ rather
than individual traces themselves. Such an algorithm is said to be $\ell$-local
if each of its statistical queries corresponds to an $\ell$-junta function over
some block of $\ell$ consecutive bits in the trace. Since several -- but not
all -- known algorithms for trace reconstruction fall under the local
statistical query paradigm, it is interesting to understand the abilities and
limitations of local SQ algorithms for trace reconstruction.
  In this paper we establish nearly-matching upper and lower bounds on local
Statistical Query algorithms for both worst-case and average-case trace
reconstruction. For the worst-case problem, we show that there is an
$\tilde{O}(n^{1/5})$-local SQ algorithm that makes all its queries with
tolerance $\tau \geq 2^{-\tilde{O}(n^{1/5})}$, and also that any
$\tilde{O}(n^{1/5})$-local SQ algorithm must make some query with tolerance
$\tau \leq 2^{-\tilde{\Omega}(n^{1/5})}$. For the average-case problem, we show
that there is an $O(\log n)$-local SQ algorithm that makes all its queries with
tolerance $\tau \geq 1/\mathrm{poly}(n)$, and also that any $O(\log n)$-local
SQ algorithm must make some query with tolerance $\tau \leq
1/\mathrm{poly}(n).$
