View source for Reduction from OV to Diameter 2 vs 3

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://people.csail.mit.edu/virgi/diam.pdf