View source for Reduction from BMM to (5/3)-approximate ap-shortest paths

FROM: [[BMM]] TO: [[(5/3)-approximate ap-shortest paths]]

== Description == 



== Implications == 

assume: BMM<br/>then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$

== Year == 

2017

== Reference == 

Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity problems. arXiv preprint arXiv:1703.01638.

https://arxiv.org/pdf/1703.01638.pdf