Before revision:  This is an improvement and a simplification upon the main result of Goldenberg, Krauthgamer, Saha, FOCS 2019], where the k vs \Theta(k^2) gap edit distance problem is solved in O(n{k}+k^3) time.
After revision:  This is an improvement and a simplification upon the result of Goldenberg, Krauthgamer, Saha, FOCS 2019], where the k vs \Theta(k^2) gap edit distance problem is solved in O(n{k}+k^3) time.