Reduction from OV to Diameter 2 vs 3
Revision as of 12:18, 15 February 2023 by Admin (talk | contribs) (Created page with "FROM: OV TO: Diameter 2 vs 3 == Description == == Implications == If: to-time: $O(N^{({2}-\epsilon)})$ where $N = nd$ and $V,E = O(n)$<br/>Then: from-time: $O((nd)^{({2}-\epsilon)}) \leq n^{({2}-\epsilon)} poly(d)$ where {2} sets of $n$ $d$-dimensional vectors == Year == 2013 == Reference == L. Roditty and V. Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In STOC, pages 515–524, 2013. https://peop...")
FROM: OV TO: Diameter 2 vs 3
Description
Implications
If: to-time: $O(N^{({2}-\epsilon)})$ where $N = nd$ and $V,E = O(n)$
Then: from-time: $O((nd)^{({2}-\epsilon)}) \leq n^{({2}-\epsilon)} poly(d)$ where {2} sets of $n$ $d$-dimensional vectors
Year
2013
Reference
L. Roditty and V. Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In STOC, pages 515–524, 2013.