Reduction from Partial Match to OV

From Algorithm Wiki
Jump to navigation Jump to search

FROM: Partial Match TO: OV

Description

Implications

If: to-time: $n^{2-\epsilon}*poly(d)$ for some $\epsilon > {0}$
Then: from-time: $n^{2-\epsilon'}*poly(d)$ for some $\epsilon' > {0}$

Year

2020

Reference

6.S078 Lecture 6

https://people.csail.mit.edu/virgi/6.s078/lecture6-post.txt