Reduction from OV to Partial Match
Revision as of 11:18, 15 February 2023 by Admin (talk | contribs) (Created page with "FROM: OV TO: Partial Match == Description == == Implications == If: to-time: $n^{2-\epsilon}*poly(d)$ for some $\epsilon > {0}$<br/>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")
FROM: OV TO: Partial Match
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