User contributions for Admin

15 February 2023

• 10:5510:55, 15 February 2023 diff hist −26‎ Reduction from CNF-SAT to Approximate Reach Centrality ‎No edit summary Tag: Reverted
• 10:5510:55, 15 February 2023 diff hist +714‎ N Reduction from CNF-SAT to Approximate Reach Centrality ‎ Created page with "FROM: CNF-SAT TO: Approximate Reach Centrality == Description == $\alpha$-approximation for any finite $\alpha$ (possibly depending on $m$) == Implications == if: to-time: $O(m^{2-\epsilon})$ for some $\epsilon > {0}$<br/>then: from-time: $O*({2}^{({1}-\delta)n})$ for some $\delta > {0}$ == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and d..."
• 10:5510:55, 15 February 2023 diff hist +720‎ N Reduction from CNF-SAT to Approximate Betweenness Centrality ‎ Created page with "FROM: CNF-SAT TO: Approximate Betweenness Centrality == Description == $\alpha$-approximation for any finite $\alpha$ (possibly depending on $m$) == Implications == if: to-time: $O(m^{2-\epsilon})$ for some $\epsilon > {0}$<br/>then: from-time: $O*({2}^{({1}-\delta)n})$ for some $\delta > {0}$ == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP..." current
• 10:5510:55, 15 February 2023 diff hist +732‎ N Reduction from CNF-SAT to Positive Betweenness Centrality ‎ Created page with "FROM: CNF-SAT TO: Positive Betweenness Centrality == Description == Positive Betweenness Centrality in directed or undirected graphs with weights in $\{1, 2\}$ == Implications == if: to-time: $O(m^{2-\epsilon})$ for some $\epsilon > {0}$<br/>then: from-time: $O*({2}^{({1}-\delta)n})$ for some $\delta > {0}$ == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality..." current
• 10:5510:55, 15 February 2023 diff hist +588‎ N Reduction from Betweenness Centrality (BC) to Diameter ‎ Created page with "FROM: Betweenness Centrality (BC) TO: Diameter == Description == == Implications == if: to-time: Truly subcubic<br/>then: from-time: Truly subcubic Monte-Carlo PTAS == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA..." current
• 10:5510:55, 15 February 2023 diff hist +556‎ N Reduction from Approximate Betweenness Centrality to Diameter ‎ Created page with "FROM: Approximate Betweenness Centrality TO: Diameter == Description == $\alpha$-approximation with $\alpha > 1$ == Implications == == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681..." current
• 10:5510:55, 15 February 2023 diff hist +556‎ N Reduction from Diameter to Approximate Betweenness Centrality ‎ Created page with "FROM: Diameter TO: Approximate Betweenness Centrality == Description == $\alpha$-approximation with $\alpha > 1$ == Implications == == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681..." current
• 10:5510:55, 15 February 2023 diff hist +601‎ N Reduction from Undirected, Weighted APSP to Undirected All-Nodes Reach Centrality ‎ Created page with "FROM: Undirected, Weighted APSP TO: Undirected All-Nodes Reach Centrality == Description == == Implications == if: to-time: Truly subcubic<br/>then: from-time: Truly subcubic == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Dieg..." current
• 10:5510:55, 15 February 2023 diff hist +616‎ N Reduction from Undirected, Weighted APSP to Undirected All-Nodes Positive Betweenness Centrality ‎ Created page with "FROM: Undirected, Weighted APSP TO: Undirected All-Nodes Positive Betweenness Centrality == Description == == Implications == if: to-time: Truly subcubic<br/>then: from-time: Truly subcubic == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA..." current
• 10:5510:55, 15 February 2023 diff hist +597‎ N Reduction from Directed, Weighted APSP to Directed All-Nodes Reach Centrality ‎ Created page with "FROM: Directed, Weighted APSP TO: Directed All-Nodes Reach Centrality == Description == == Implications == if: to-time: Truly subcubic<br/>then: from-time: Truly subcubic == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, C..." current
• 10:5510:55, 15 February 2023 diff hist +612‎ N Reduction from Directed, Weighted APSP to Directed All-Nodes Positive Betweenness Centrality ‎ Created page with "FROM: Directed, Weighted APSP TO: Directed All-Nodes Positive Betweenness Centrality == Description == == Implications == if: to-time: Truly subcubic<br/>then: from-time: Truly subcubic == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 201..." current
• 10:5510:55, 15 February 2023 diff hist +739‎ N Reduction from Negative Triangle Detection to All-Nodes Positive Betweenness Centrality ‎ Created page with "FROM: Negative Triangle Detection TO: All-Nodes Positive Betweenness Centrality == Description == == Implications == if: to-time: $\tilde{O}(T(n,m,M))$ for $n$-node $m$-edge graph with integer weights in $(-M,M)$<br/>then: from-time: $\tilde{O}(T(n,m,M))$ for $n$-node $m$-edge graph with integer weights in $(-M,M)$ == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph ce..." current
• 10:5510:55, 15 February 2023 diff hist +704‎ N Reduction from Reach Centrality to Positive Betweenness Centrality ‎ Created page with "FROM: Reach Centrality TO: Positive Betweenness Centrality == Description == == Implications == if: to-time: $\tilde{O}(T(n,m))$ for $n$-node $m$-edge directed (resp. undirected) graph<br/>then: from-time: $\tilde{O}(T(n,m))$ for $n$-node $m$-edge directed (resp. undirected) graph == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diamete..." current
• 10:5510:55, 15 February 2023 diff hist +766‎ N Reduction from Positive Betweenness Centrality to Diameter ‎ Created page with "FROM: Positive Betweenness Centrality TO: Diameter == Description == == Implications == if: to-time: $\tilde{O}(T(n,m,M))$ for $n$-node $m$-edge directed (resp. undirected) graph with integer weights in $(-M,M)$<br/>then: from-time: $\tilde{O}(T(n,m,M))$ for $n$-node $m$-edge directed (resp. undirected) graph with integer weights in $(-M,M)$ == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic eq..." current
• 10:5510:55, 15 February 2023 diff hist +251‎ Reduction from Reach Centrality to Diameter ‎No edit summary Tag: Reverted
• 10:5510:55, 15 February 2023 diff hist +696‎ N Reduction from Diameter to Positive Betweenness Centrality ‎ Created page with "FROM: Diameter TO: Positive Betweenness Centrality == Description == == Implications == if: to-time: $\tilde{O}(T(n,m))$ for $n$-node $m$-edge directed (resp. undirected) graph<br/>then: from-time: $\tilde{O}(T(n,m))$ for $n$-node $m$-edge directed (resp. undirected) graph == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Pr..." current
• 10:5510:55, 15 February 2023 diff hist +587‎ N Reduction from Undirected, Weighted APSP to All-Nodes Median Parity ‎ Created page with "FROM: Undirected, Weighted APSP TO: All-Nodes Median Parity == Description == == Implications == if: to-time: Truly subcubic<br/>then: from-time: Truly subcubic == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, Ja..." current
• 10:5510:55, 15 February 2023 diff hist +681‎ N Reduction from Diameter to Reach Centrality ‎ Created page with "FROM: Diameter TO: Reach Centrality == Description == == Implications == if: to-time: $\tilde{O}(T(n,m))$ for $n$-node $m$-edge directed (resp. undirected) graph<br/>then: from-time: $\tilde{O}(T(n,m))$ for $n$-node $m$-edge directed (resp. undirected) graph == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of th..." current
• 10:5510:55, 15 February 2023 diff hist +585‎ N Reduction from Directed, Weighted APSP to All-Nodes Median Parity ‎ Created page with "FROM: Directed, Weighted APSP TO: All-Nodes Median Parity == Description == == Implications == if: to-time: Truly subcubic<br/>then: from-time: Truly subcubic == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, Janu..." current
• 10:5510:55, 15 February 2023 diff hist +643‎ N Reduction from Negative Triangle Detection to Radius ‎ Created page with "FROM: Negative Triangle Detection TO: Radius == Description == == Implications == if: to-time: $\tilde{O}(T(n,m,M))$ for $n$-node $m$-edge graph with integer weights in $(-M,M)$<br/>then: from-time: $\tilde{O}(T(n,m,M))$ == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposi..." current
• 10:5510:55, 15 February 2023 diff hist +656‎ N Reduction from Negative Triangle Detection to All-Nodes Median Parity ‎ Created page with "FROM: Negative Triangle Detection TO: All-Nodes Median Parity == Description == == Implications == if: to-time: $\tilde{O}(T(n,M))$ for $n$-node $m$-edge graph with integer weights in $(-M, M)$<br/>then: from-time: $\tilde{O}T(n,M))$ == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM..." current
• 10:5510:55, 15 February 2023 diff hist +639‎ N Reduction from Negative Triangle Detection to Median ‎ Created page with "FROM: Negative Triangle Detection TO: Median == Description == == Implications == if: to-time: $\tilde{O}(T(n,M))$ for $n$-node $m$-edge graph with integer weights in $(-M, M)$<br/>then: from-time: $\tilde{O}T(n,M))$ == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium o..." current
• 10:5510:55, 15 February 2023 diff hist +626‎ N Reduction from Negative Triangle Detection to Betweenness Centrality (BC) ‎ Created page with "FROM: Negative Triangle Detection TO: Betweenness Centrality (BC) == Description == == Implications == if: to-time: $\tilde{O}(T(n,m))$ for $n$-node $m$-edge graph<br/>then: from-time: $\tilde{O}T(n,m))$ == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Al..." current
• 10:5510:55, 15 February 2023 diff hist +493‎ N Reduction from CNF-SAT to Approximate Diameter ‎ Created page with "FROM: CNF-SAT TO: Approximate Diameter == Description == == Implications == if: to-time: $O(m^{2-\epsilon})$ for some $\epsilon > {0}$ for a $({3}/{2} - \epsilon)$-approximation<br/>then: from-time: $O*(({2}-\delta)^n)$ for constant $\delta > {0}$ == Year == 2013 == Reference == L. Roditty and V. Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In STOC, pages 515–524, 2013. https://people.csail.mit...." current
• 10:5510:55, 15 February 2023 diff hist +486‎ N Reduction from Reach Centrality to Diameter ‎ Created page with "FROM: Reach Centrality TO: Diameter == Description == == Implications == == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681–1697, 2015. https://epubs.siam.org/doi/10.1137/1.9781611..."
• 10:5510:55, 15 February 2023 diff hist +514‎ N Reduction from Betweenness Centrality (BC) to Undirected, Weighted APSP ‎ Created page with "FROM: Betweenness Centrality (BC) TO: Undirected, Weighted APSP == Description == == Implications == == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681–1697, 2015. https://epubs.si..." current
• 10:5510:55, 15 February 2023 diff hist +500‎ N Reduction from Directed Median to Directed, Weighted APSP ‎ Created page with "FROM: Directed Median TO: Directed, Weighted APSP == Description == == Implications == == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681–1697, 2015. https://epubs.siam.org/doi/10...." current
• 10:5510:55, 15 February 2023 diff hist +512‎ N Reduction from Betweenness Centrality (BC) to Directed, Weighted APSP ‎ Created page with "FROM: Betweenness Centrality (BC) TO: Directed, Weighted APSP == Description == == Implications == == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681–1697, 2015. https://epubs.siam..." current
• 10:5510:55, 15 February 2023 diff hist +504‎ N Reduction from Undirected Median to Undirected, Weighted APSP ‎ Created page with "FROM: Undirected Median TO: Undirected, Weighted APSP == Description == == Implications == == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681–1697, 2015. https://epubs.siam.org/doi..." current
• 10:5510:55, 15 February 2023 diff hist +504‎ N Reduction from Undirected Radius to Undirected, Weighted APSP ‎ Created page with "FROM: Undirected Radius TO: Undirected, Weighted APSP == Description == == Implications == == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681–1697, 2015. https://epubs.siam.org/doi..." current
• 10:5510:55, 15 February 2023 diff hist +500‎ N Reduction from Directed Radius to Directed, Weighted APSP ‎ Created page with "FROM: Directed Radius TO: Directed, Weighted APSP == Description == == Implications == == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681–1697, 2015. https://epubs.siam.org/doi/10...." current
• 10:5510:55, 15 February 2023 diff hist +177‎ N Reduction from 3SUM to All-Integers 3SUM ‎ Created page with "FROM: 3SUM TO: All-Integers 3SUM == Description == == Implications == if: to-time: $T(n)$<br/>then: from-time: $O(T(n))$ == Year == == Reference == Trivial" current
• 10:5510:55, 15 February 2023 diff hist +398‎ N Reduction from All-Integers 3SUM to 3SUM ‎ Created page with "FROM: All-Integers 3SUM TO: 3SUM == Description == == Implications == if: to-time: $O(n^{2-\epsilon})$ for some $\epsilon > {0}$<br/>then: from-time: $O(n^{1.5} + n^{2-\epsilon / 2})$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 8.1" current
• 10:5510:55, 15 February 2023 diff hist +410‎ N Reduction from $(\min, \leq)$ Product to Triangle in Unweighted Graph ‎ Created page with "FROM: $(\min, \leq)$ Product TO: Triangle in Unweighted Graph == Description == == Implications == if: to-time: $T(n)$ for unweighted graph<br/>then: from-time: $O(n^{3/2} \sqrt{T(O(n))} \log n)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 7.1" current
• 10:5510:55, 15 February 2023 diff hist +403‎ N Reduction from Nondecreasing Triangle to Triangle in Unweighted Graph ‎ Created page with "FROM: Nondecreasing Triangle TO: Triangle in Unweighted Graph == Description == == Implications == if: to-time: $T(n)$ for unweighted graph<br/>then: from-time: $O(n^{3/2} \sqrt{T(O(n))})$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 7.1" current
• 10:5510:55, 15 February 2023 diff hist +503‎ N Reduction from Negative Triangle to Price Query ‎ Created page with "FROM: Negative Triangle TO: Price Query == Description == == Implications == if: to-time: $O(n^{2} / f(n))$ to answer any subsequent price query after $n$-node edge-weighted graph is preprocessed in $O(^k)$ time for some constant $k > {0}$<br/>then: from-time: $O(n^{3} / f(n^{1/({2}k)})$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/..." current
• 10:5510:55, 15 February 2023 diff hist +513‎ N Reduction from BMM to Independent Set Queries ‎ Created page with "FROM: BMM TO: Independent Set Queries == Description == == Implications == if: to-time: $O(n^{2} / \log^c n)$ to answer all subsequent batches of $\log n$ independent set queries from a graph that takes $O(n^k)$ time to preprocess for some $c,k > {0}$<br/>then: from-time: $O(n^{3} / \log^{c+1} n)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.or..." current
• 10:5510:55, 15 February 2023 diff hist +528‎ N Reduction from Triangle Detection to Independent Set Queries ‎ Created page with "FROM: Triangle Detection TO: Independent Set Queries == Description == == Implications == if: to-time: $O(n^{2} / \log^c n)$ to answer all subsequent batches of $\log n$ independent set queries from a graph that takes $O(n^k)$ time to preprocess for some $c,k > {0}$<br/>then: from-time: $O(n^{3} / \log^{c+1} n)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. ht..." current
• 10:5510:55, 15 February 2023 diff hist +494‎ N Reduction from Directed, Weighted APSP to Replacement Paths Problem (RPP) ‎ Created page with "FROM: Directed, Weighted APSP TO: Replacement Paths Problem (RPP) == Description == == Implications == if: to-time: $T(n) polylog M$ in graphs with integer weights in $({0}, M)$<br/>then: from-time: $O(n^{2} T(O(n^{1/3})) polylog M)$ in graphs with integer weights in $(-M, M)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/318..." current
• 10:5510:55, 15 February 2023 diff hist +503‎ N Reduction from Distance Product to Second Shortest Simple Path ‎ Created page with "FROM: Distance Product TO: Second Shortest Simple Path == Description == == Implications == if: to-time: $T(n,W)$ where there are $n$ nodes and integer weights in $({0}, W)$<br/>then: from-time: $O(n^{2} T(O(n^{1/3}), O(nW)) \log W)$ for two $n\times n$ matrices with weights in $(-W, W)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/..." current
• 10:5510:55, 15 February 2023 diff hist +497‎ N Reduction from Directed, Weighted APSP to Second Shortest Simple Path ‎ Created page with "FROM: Directed, Weighted APSP TO: Second Shortest Simple Path == Description == == Implications == if: to-time: $T(n,W)$ where there are $n$ nodes and integer weights in $({0}, W)$<br/>then: from-time: $O(n^{2} T(O(n^{1/3}), O(n^{2}W)) \log Wn)$ for graphs with weights in $(-W, W)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.114..." current
• 10:5510:55, 15 February 2023 diff hist +479‎ N Reduction from Minimum Triangle to Second Shortest Simple Path ‎ Created page with "FROM: Minimum Triangle TO: Second Shortest Simple Path == Description == == Implications == if: to-time: $T(n,W)$ where there are $n$ nodes and integer weights in $({0}, W)$<br/>then: from-time: $T(O(n), O(nW))$ for $n$ node graph with integer weights in $(-W, W)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem..." current
• 10:5510:55, 15 February 2023 diff hist +411‎ N Reduction from Maximum Subarray to Negative Triangle Detection ‎ Created page with "FROM: Maximum Subarray TO: Negative Triangle Detection == Description == == Implications == == Year == 1998 == Reference == Hisao Tamaki and Takeshi Tokuyama. 1998. Algorithms for the maximum subarray problem based on matrix multiplication. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’98). 446–452. https://dl.acm.org/doi/abs/10.5555/314613.314823" current
• 10:5510:55, 15 February 2023 diff hist +307‎ N Reduction from Negative Triangle Detection to Maximum Subarray ‎ Created page with "FROM: Negative Triangle Detection TO: Maximum Subarray == Description == == Implications == == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 5.4" current
• 10:5510:55, 15 February 2023 diff hist +463‎ N Reduction from Negative Triangle Detection to Shortest Cycle ‎ Created page with "FROM: Negative Triangle Detection TO: Shortest Cycle == Description == == Implications == if: to-time: $T(n,M)$ where there are $n$ nodes and weights in $({1}, M)$<br/>then: from-time: $T(n, O(M))$ where there are $n$ nodes and weights in $(-M, M)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 5.3" current
• 10:5510:55, 15 February 2023 diff hist +494‎ N Reduction from Negative Triangle Detection to Metricity ‎ Created page with "FROM: Negative Triangle Detection TO: Metricity == Description == == Implications == if: to-time: $O(n^{2}) + T(O(n), O(M))$ where the metricity problem is on $(n)$ s.t. all distances are in $(-M, M)$, and $T(n,M)$ is nondecreasing<br/>then: from-time: $O(n^{2}) + T(O(n), O(M))$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3..." current
• 10:5510:55, 15 February 2023 diff hist +495‎ N Reduction from Metricity to Negative Triangle Detection ‎ Created page with "FROM: Metricity TO: Negative Triangle Detection == Description == == Implications == if: to-time: $O(n^{2}) + T(O(n), O(M))$ where $T(n,M)$ is nondecreasing<br/>then: from-time: $O(n^{2}) + T(O(n), O(M))$ where the metricity problem is on $(n)$ s.t. all distances are in $(-M, M)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/..." current
• 10:5510:55, 15 February 2023 diff hist +450‎ N Reduction from Directed, Weighted APSP to Undirected, Weighted APSP ‎ Created page with "FROM: Directed, Weighted APSP TO: Undirected, Weighted APSP == Description == == Implications == if: to-time: $T(n, \Theta(M))$ where digraph has weights in $(-M, M)$<br/>then: from-time: $T(n, M)$ where graph has weights in $({0}, M)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 5.1" current
• 10:5510:55, 15 February 2023 diff hist +450‎ N Reduction from Undirected, Weighted APSP to Directed, Weighted APSP ‎ Created page with "FROM: Undirected, Weighted APSP TO: Directed, Weighted APSP == Description == == Implications == if: to-time: $T(n, M)$ where graph has weights in $({0}, M)$<br/>then: from-time: $T(n, \Theta(M))$ where digraph has weights in $(-M, M)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 5.1" current
• 10:5510:55, 15 February 2023 diff hist +382‎ N Reduction from All Pairs Minimum Witness (APMW) to Negative Triangle Detection ‎ Created page with "FROM: All Pairs Minimum Witness (APMW) TO: Negative Triangle Detection == Description == == Implications == if: to-time: $T(n)$<br/>then: from-time: $O(T(n^{1/3})n^{2})$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Lemma 4.5" current