Reduction from BMM to 1-sensitive incremental ss-reach

FROM: BMM TO: 1-sensitive incremental ss-reach

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.

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