New pages

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

• 10:55, 15 February 2023 ‎Reduction from MAX-CNF-SAT to Maximum Local Edge Connectivity (hist | edit) ‎[480 bytes] ‎Admin (talk | contribs) (Created page with "FROM: MAX-CNF-SAT TO: Maximum Local Edge Connectivity == Description == == Implications == assume: SETH<br/>then: for any $\epsilon > {0}$, in graphs with $n$ nodes and $\tilde{O}(n)$ edges, target cannot be solved in time $O(n^{2-\epsilon})$ == Year == 2018 == Reference == Krauthgamer, R., & Trabelsi, O. (2018). Conditional lower bounds for all-pairs max-flow. ACM Transactions on Algorithms (TALG), 14(4), 1-15. https://dl.acm.org/doi/abs/10.1145/32...")
• 10:55, 15 February 2023 ‎Reduction from MAX-CNF-SAT to All-Pairs Maximum Flow (hist | edit) ‎[602 bytes] ‎Admin (talk | contribs) (Created page with "FROM: MAX-CNF-SAT TO: All-Pairs Maximum Flow == Description == == Implications == assume: SETH<br/>then: for any fixed $\epsilon > {0}$, in graphs with $n$ nodes, $m=O(n)$ edges, and capacities in $\{1,\cdots,n\}$ target cannot be solved in time $O((n^{2}m)^{1-\epsilon})$ == Year == 2018 == Reference == Krauthgamer, R., & Trabelsi, O. (2018). Conditional lower bounds for all-pairs max-flow. ACM Transactions on Algorithms (TALG), 14(4), 1-15. https:/...")
• 10:55, 15 February 2023 ‎Reduction from MAX-CNF-SAT to st-Maximum Flow (hist | edit) ‎[503 bytes] ‎Admin (talk | contribs) (Created page with "FROM: MAX-CNF-SAT TO: st-Maximum Flow == Description == == Implications == assume: SETH<br/>then: for any fixed constants $\epsilon > {0}$, $c_1,c_2 \in ({0},{1})$, on graphs with $n$ nodes $|S|=\tilde{\Theta}(n^{c_1})$, $|T|=\tilde{\Theta(n^{c_2})}$, $m=O(n)$ edges, and capacaties in $\{1,\cdots,n\}$, target cannot be solved in $O((|S|T|m)^{1-\epsilon})$ == Year == 2018 == Reference == Krauthgamer, R., & Trabelsi, O. (2018). Conditional lower bounds...")
• 10:55, 15 February 2023 ‎Reduction from Directed, Weighted APSP to Dynamic Bipartite Maximum-Weight Matching (hist | edit) ‎[676 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Directed, Weighted APSP TO: Dynamic Bipartite Maximum-Weight Matching == Description == == Implications == if: to-time: amortized $O(n^{2-\epsilon})$ update and query times in decremental or incremental graphs<br/>then: APSP Hypothesis 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 Directed, Weighted APSP to Dynamic $st$-Shortest Path (hist | edit) ‎[661 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Directed, Weighted APSP TO: Dynamic $st$-Shortest Path == Description == == Implications == if: to-time: amortized $O(n^{2-\epsilon})$ update and query times in decremental or incremental graphs<br/>then: APSP Hypothesis 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 Scien...")
• 10:55, 15 February 2023 ‎Reduction from Triangle Detection to Dynamic Bipartite Maximum-Weight Matching (hist | edit) ‎[767 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Triangle Detection TO: Dynamic Bipartite Maximum-Weight Matching == 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 stro...")
• 10:55, 15 February 2023 ‎Reduction from Triangle Detection to Strong Connectivity (dynamic) (hist | edit) ‎[755 bytes] ‎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...")
• 10:55, 15 February 2023 ‎Reduction from Triangle Detection to Dynamic st-Reach (hist | edit) ‎[791 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Triangle Detection TO: Dynamic st-Reach == Description == == Implications == assume: SETH<br/>then: for any fixed constants $\epsilon > {0}$, $c_1,c_2 \in ({0},{1})$, on graphs with $n$ nodes $|S|=\tilde{\Theta}(n^{c_1})$, $|T|=\tilde{\Theta(n^{c_2})}$, $m=O(n)$ edges, and capacaties in $\{1,\cdots,n\}$, target cannot be solved in $O((|S|T|m)^{1-\epsilon})$ == Year == 2014 == Reference == Abboud, Amir, and Virginia Vassilevska Williams. "Popula...")
• 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/...")

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