New pages

(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)

• 10:55, 15 February 2023 ‎Reduction from CNF-SAT to Dynamic ST-Reach (hist | edit) ‎[672 bytes] ‎Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Dynamic ST-Reach == Description == == Implications == if: to-time: $O(m^{2-\epsilon})$ amrotized update and query times, for any $\epsilon > {0}$, even after arbitrarily long polynomial time preprocessing<br/>then: SETH 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 Com...")
• 10:55, 15 February 2023 ‎Reduction from CNF-SAT to Dynamic 4/3-Diameter (hist | edit) ‎[676 bytes] ‎Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Dynamic 4/3-Diameter == Description == == Implications == if: to-time: $O(m^{2-\epsilon})$ amrotized update and query times, for any $\epsilon > {0}$, even after arbitrarily long polynomial time preprocessing<br/>then: SETH 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...")
• 10:55, 15 February 2023 ‎Reduction from CNF-SAT to Dynamic Connected Subgraph (hist | edit) ‎[699 bytes] ‎Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Dynamic Connected Subgraph == Description == == Implications == if: to-time: $O(m^{1-\epsilon})$ amrotized update and query times on sparse graphs, for any $\epsilon > {0}$, even after arbitrarily long polynomial time preprocessing<br/>then: SETH 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 Symp...")
• 10:55, 15 February 2023 ‎Reduction from CNF-SAT to (hist | edit) ‎[677 bytes] ‎Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: #SSR == Description == == Implications == if: to-time: $O(m^{1-\epsilon})$ amrotized update and query times on sparse graphs, for any $\epsilon > {0}$, even after arbitrarily long polynomial time preprocessing<br/>then: SETH 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 o...")
• 10:55, 15 February 2023 ‎Reduction from CNF-SAT to Dynamic MaxSCC (hist | edit) ‎[687 bytes] ‎Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Dynamic MaxSCC == Description == == Implications == if: to-time: $O(m^{1-\epsilon})$ amrotized update and query times on sparse graphs, for any $\epsilon > {0}$, even after arbitrarily long polynomial time preprocessing<br/>then: SETH 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 Fou...")
• 10:55, 15 February 2023 ‎Reduction from CNF-SAT to SC2 (hist | edit) ‎[676 bytes] ‎Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: SC2 == Description == == Implications == if: to-time: $O(m^{1-\epsilon})$ amrotized update and query times on sparse graphs, for any $\epsilon > {0}$, even after arbitrarily long polynomial time preprocessing<br/>then: SETH 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...")
• 10:55, 15 February 2023 ‎Reduction from Min-Weight k-Clique to Minimum Weight k-Cycle (hist | edit) ‎[635 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Min-Weight k-Clique TO: Minimum Weight k-Cycle == Description == == Implications == if: to-time: $O(nm^{\lceil k/{2} \rceil / \lambda - \epsilon})$ for any $\epsilon > {0}$ for $m = \Theta(n^{1+{1}/(\lambda - {1})}) edges and $n$ nodes where $\lambda = k - \lceil k/{2} \rceil + {1}$<br/>then: from-time: $O(n^{k - \epsilon})$ for some $\epsilon > {0}$ == Year == 2018 == Reference == Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Will...")
• 10:55, 15 February 2023 ‎Reduction from Min-Weight k-Cycle to Undirected Wiener Index (hist | edit) ‎[450 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Min-Weight k-Cycle TO: Undirected Wiener Index == Description == == Implications == if: to-time: $f(N,M)$ for N nodes, M edges<br/>then: from-time: $\tilde{O}(f(N,M)+M)$ == Year == 2018 == Reference == Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Proc. SODA, page to appear, 2018. https://arxiv.org/pdf/1712.08147v2.pdf, Theorem B.2")
• 10:55, 15 February 2023 ‎Reduction from CNF-SAT to Approximate Betweenness Centrality (hist | edit) ‎[720 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from CNF-SAT to Approximate Reach Centrality (hist | edit) ‎[688 bytes] ‎Admin (talk | contribs) (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:55, 15 February 2023 ‎Reduction from CNF-SAT to Positive Betweenness Centrality (hist | edit) ‎[732 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Betweenness Centrality (BC) to Diameter (hist | edit) ‎[588 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Approximate Betweenness Centrality to Diameter (hist | edit) ‎[556 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Diameter to Approximate Betweenness Centrality (hist | edit) ‎[556 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Directed, Weighted APSP to Directed All-Nodes Reach Centrality (hist | edit) ‎[597 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Undirected, Weighted APSP to Undirected All-Nodes Reach Centrality (hist | edit) ‎[601 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Undirected, Weighted APSP to Undirected All-Nodes Positive Betweenness Centrality (hist | edit) ‎[616 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Negative Triangle Detection to All-Nodes Positive Betweenness Centrality (hist | edit) ‎[739 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Directed, Weighted APSP to Directed All-Nodes Positive Betweenness Centrality (hist | edit) ‎[612 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Reach Centrality to Positive Betweenness Centrality (hist | edit) ‎[704 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Positive Betweenness Centrality to Diameter (hist | edit) ‎[766 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Diameter to Positive Betweenness Centrality (hist | edit) ‎[696 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Diameter to Reach Centrality (hist | edit) ‎[681 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Undirected, Weighted APSP to All-Nodes Median Parity (hist | edit) ‎[587 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Directed, Weighted APSP to All-Nodes Median Parity (hist | edit) ‎[585 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Negative Triangle Detection to Radius (hist | edit) ‎[643 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Negative Triangle Detection to Median (hist | edit) ‎[639 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Negative Triangle Detection to All-Nodes Median Parity (hist | edit) ‎[656 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Negative Triangle Detection to Betweenness Centrality (BC) (hist | edit) ‎[626 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from CNF-SAT to Approximate Diameter (hist | edit) ‎[493 bytes] ‎Admin (talk | contribs) (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....")
• 10:55, 15 February 2023 ‎Reduction from Reach Centrality to Diameter (hist | edit) ‎[737 bytes] ‎Admin (talk | contribs) (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:55, 15 February 2023 ‎Reduction from Betweenness Centrality (BC) to Undirected, Weighted APSP (hist | edit) ‎[514 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Betweenness Centrality (BC) to Directed, Weighted APSP (hist | edit) ‎[512 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Directed Median to Directed, Weighted APSP (hist | edit) ‎[500 bytes] ‎Admin (talk | contribs) (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....")
• 10:55, 15 February 2023 ‎Reduction from Undirected Median to Undirected, Weighted APSP (hist | edit) ‎[504 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Undirected Radius to Undirected, Weighted APSP (hist | edit) ‎[504 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Directed Radius to Directed, Weighted APSP (hist | edit) ‎[500 bytes] ‎Admin (talk | contribs) (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....")
• 10:55, 15 February 2023 ‎Reduction from All-Integers 3SUM to 3SUM (hist | edit) ‎[398 bytes] ‎Admin (talk | contribs) (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")
• 10:55, 15 February 2023 ‎Reduction from 3SUM to All-Integers 3SUM (hist | edit) ‎[177 bytes] ‎Admin (talk | contribs) (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")
• 10:55, 15 February 2023 ‎Reduction from Nondecreasing Triangle to Triangle in Unweighted Graph (hist | edit) ‎[403 bytes] ‎Admin (talk | contribs) (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")
• 10:55, 15 February 2023 ‎Reduction from $(\min, \leq)$ Product to Triangle in Unweighted Graph (hist | edit) ‎[410 bytes] ‎Admin (talk | contribs) (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")
• 10:55, 15 February 2023 ‎Reduction from Negative Triangle to Price Query (hist | edit) ‎[503 bytes] ‎Admin (talk | contribs) (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/...")
• 10:55, 15 February 2023 ‎Reduction from BMM to Independent Set Queries (hist | edit) ‎[513 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Triangle Detection to Independent Set Queries (hist | edit) ‎[528 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Directed, Weighted APSP to Replacement Paths Problem (RPP) (hist | edit) ‎[494 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Distance Product to Second Shortest Simple Path (hist | edit) ‎[503 bytes] ‎Admin (talk | contribs) (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/...")
• 10:55, 15 February 2023 ‎Reduction from Directed, Weighted APSP to Second Shortest Simple Path (hist | edit) ‎[497 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Minimum Triangle to Second Shortest Simple Path (hist | edit) ‎[479 bytes] ‎Admin (talk | contribs) (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...")
• 10:55, 15 February 2023 ‎Reduction from Maximum Subarray to Negative Triangle Detection (hist | edit) ‎[411 bytes] ‎Admin (talk | contribs) (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")
• 10:55, 15 February 2023 ‎Reduction from Negative Triangle Detection to Maximum Subarray (hist | edit) ‎[307 bytes] ‎Admin (talk | contribs) (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")

(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)