apsp_hypothesis (466B)
1 # APSP hypothesis 2 3 [hypothesis] that [all_pairs_shortest_path] (also involving negative weights) requires time n^{3-o(1)} 4 - implies [exact_triangle] 5 - equivalent to [negative_triangle] 6 - you can use [all_pairs_shortest_path] to compute [negative_triangle] 7 - other direction more involved 8 - equivalent to [mpp_minimum] 9 10 The equivalences to [all_pairs_shortest_path] and [mpp_minimum] are from [williams2018subcubic] 11 12 Up: [hypothesis] on [all_pairs_shortest_path]