Reduction from OV to Diameter 2 vs 3

FROM: OV TO: Diameter 2 vs 3

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.

https://people.csail.mit.edu/virgi/diam.pdf