Reduction from BMM to (5/3)-approximate ap-shortest paths
Revision as of 11:19, 15 February 2023 by Admin (talk | contribs) (Created page with "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. htt...")
FROM: BMM TO: (5/3)-approximate ap-shortest paths
Description
Implications
assume: BMM
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.