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 Õ(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 Õ(n/k^{c−0.5}) whenever c ≥ 1.5. For 1 < c < 1.5, the running time of our algorithm is Õ(n/k^{2c−1}). In the restricted case of k^c = Ω(n), this matches a known result [Batu, Ergün, 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 k and c.
This is joint work with Elazar Goldenberg, Robert Krauthgamer, and Barna Saha. To be presented at FOCS 2022, with the full version available at https://arxiv.org/abs/2111.12706v2.