apsp_hypothesis (557B)
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] (find if the minimum diagonal entry of the min-plus product of three matrices A B C is <0) 9 10 The equivalences to [all_pairs_shortest_path] and [mpp_minimum] are from [williams2018subcubic] 11 12 Up: [hypothesis] on [all_pairs_shortest_path]