Reduction from UOV to Longest Common Subsequence

FROM: UOV TO: Longest Common Subsequence

Implications

If: to-time: $O((nm)^{({1}-\epsilon)})$, where $|x| = O(nd)$ and $|y| = O(md)$
Then: from-time: $O((nm)^{({1}-\epsilon/{2})})$

Year

2015

Reference

https://arxiv.org/pdf/1502.01063.pdf