Reduction from OV to Edit Distance: Difference between revisions
Jump to navigation
Jump to search
(Created page with "FROM: OV TO: Edit Distance == Description == == Implications == If: to-time: $O(n^{({2}-\epsilon)})$ where $n$ is length of sequence<br/>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 Theo...") |
No edit summary |
||
| Line 7: | Line 7: | ||
== Implications == | == Implications == | ||
If: to-time: $O(n^{({2}-\epsilon)})$ where $n$ is length of sequence<br/>Then: from-time: $O(d^ | If: to-time: $O(n^{({2}-\epsilon)})$ where $n$ is length of sequence<br/>Then: from-time: $O(d^{O({1})}*(N)^{({2}-\epsilon)})$ where ${2}$ sets of $n$ $d$-dimensional vectors | ||
== Year == | == Year == | ||
Latest revision as of 09:57, 10 April 2023
FROM: OV TO: Edit Distance
Description
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.