Reduction from OV to Edit Distance

FROM: OV TO: Edit Distance

Implications

If: to-time: $O(n^{({2}-\epsilon)})$ where $n$ is length of sequence
Then: from-time: $O(d^{O({1})}*(N)^{({2}-\epsilon)})$ where ${2}$ sets of $n$ $d$-dimensional vectors

Year

2014

Reference

Backurs, Arturs, and Piotr Indyk. "Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)." Proceedings of the forty-seventh annual ACM symposium on Theory of computing. 2015.

https://arxiv.org/pdf/1412.0348.pdf