Reduction from Triangle Detection to Strong Connectivity (dynamic)
Revision as of 10:55, 15 February 2023 by Admin (talk | contribs) (Created page with "FROM: Triangle Detection TO: Strong Connectivity (dynamic) == Description == == Implications == let $\gamma = (w-{1})/(w+{1}) \in ({1}/{3},{0.408})$<br/>if: to-time: $O(m^{2\gamma-\epsilon})$ update and query times even after O(m^{1+\gamma-\epsilon}) preprocessing time for any $\epsilon > {0}$<br/>then: Strong Triangle is false == Year == 2014 == Reference == Abboud, Amir, and Virginia Vassilevska Williams. "Popular conjectures imply strong lower bou...")
FROM: Triangle Detection TO: Strong Connectivity (dynamic)
Description
Implications
let $\gamma = (w-{1})/(w+{1}) \in ({1}/{3},{0.408})$
if: to-time: $O(m^{2\gamma-\epsilon})$ update and query times even after O(m^{1+\gamma-\epsilon}) preprocessing time for any $\epsilon > {0}$
then: Strong Triangle is false
Year
2014
Reference
Abboud, Amir, and Virginia Vassilevska Williams. "Popular conjectures imply strong lower bounds for dynamic problems." In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 434-443. IEEE, 2014.