View source for All Pairs Shortest Paths Hypothesis (APSP Hypothesis)

== Target Problem == 

[[APSP]]

== Description == 

No randomized algorithm can solve APSP in $O(n^{3-\epsilon})$ time for $\epsilon > 0$ on $n$ node graphs with edge weights in $\{-n^c,\ldots,n^c\}$ and no negative cycles for large enough $c$.

== Implies the following Hypothesis == 



== Implied by the following Hypothesis == 



== Computation Model == 

Word-RAM on $\log(n)$ bit words

== Proven? == 

No

== Year == 



== References/Citation == 

http://people.csail.mit.edu/virgi/eccentri.pdf Hypothesis 3