  We study the problem of approximating edit distance in sublinear time. This
is formalized as the $(k,k^c)$-Gap Edit Distance problem, where the input is a
pair of strings $X,Y$ and parameters $k,c>1$, and the goal is to return YES if
$ED(X,Y)\leq k$, NO if $ED(X,Y)> k^c$, and an arbitrary answer when $k <
ED(X,Y) \le k^c$. Recent years have witnessed significant interest in designing
sublinear-time algorithms for Gap Edit Distance.
  In this work, we resolve the non-adaptive query complexity of Gap Edit
Distance for the entire range of parameters, improving over a sequence of
previous results. Specifically, we design a non-adaptive algorithm with query
complexity $\tilde{O}(n/k^{c-0.5})$, and we further prove that this bound is
optimal up to polylogarithmic factors.
  Our algorithm also achieves optimal time complexity $\tilde{O}(n/k^{c-0.5})$
whenever $c\geq 1.5$. For $1<c<1.5$, the running time of our algorithm is
$\tilde{O}(n/k^{2c-1})$. In the restricted case of $k^c=\Omega(n)$, this
matches a known result [Batu, Erg\"un, Kilian, Magen, Raskhodnikova, Rubinfeld,
and Sami; STOC 2003], and in all other (nontrivial) cases, our running time is
strictly better than all previous algorithms, including the adaptive ones.
However, an independent work of Bringmann, Cassis, Fischer, and Nakos [STOC
2022] provides an adaptive algorithm that bypasses the non-adaptive lower
bound, but only for small enough $k$ and $c$.
