Reduction from Triangle Detection to Strong Connectivity (dynamic): Revision history

Jump to navigation Jump to search

Diff selection: Mark the radio buttons of the revisions to compare and hit enter or the button at the bottom.
Legend: (cur) = difference with latest revision, (prev) = difference with preceding revision, m = minor edit.

    15 February 2023

    • curprev 10:5510:55, 15 February 2023‎ Admin talk contribs‎ 755 bytes +755‎ 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..."
Retrieved from "https://algorithm-wiki.csail.mit.edu/wiki/Reduction_from_Triangle_Detection_to_Strong_Connectivity_(dynamic)"