Reduction from 3SUM to Local Alignment
Revision as of 10:55, 15 February 2023 by Admin (talk | contribs) (Created page with "FROM: 3SUM TO: Local Alignment == Description == == Implications == if: to-time $N^{2-\delta-\epsilon} for two strings of size $n$ and alphabet of size $n^{1-\delta}$ for some $\espilon > {0}$,$\delta \in ({0},{1})$<br/>then: from-time: $n^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 2014 == Reference == Abboud, Amir, Virginia Vassilevska Williams, and Oren Weimann. "Consequences of faster alignment of sequences." In International Colloquium...")
FROM: 3SUM TO: Local Alignment
Description
Implications
if: to-time $N^{2-\delta-\epsilon} for two strings of size $n$ and alphabet of size $n^{1-\delta}$ for some $\espilon > {0}$,$\delta \in ({0},{1})$
then: from-time: $n^{2-\epsilon'}$ for some $\epsilon' > {0}$
Year
2014
Reference
Abboud, Amir, Virginia Vassilevska Williams, and Oren Weimann. "Consequences of faster alignment of sequences." In International Colloquium on Automata, Languages, and Programming, pp. 39-51. Springer, Berlin, Heidelberg, 2014.
https://link.springer.com/chapter/10.1007/978-3-662-43948-7_4