User contributions for Admin

15 February 2023

• 11:1311:13, 15 February 2023 diff hist +12‎ Czumaj (Approximate MCOP Matrix Chain Multiplication) ‎No edit summary Tags: Manual revert Reverted
• 11:1311:13, 15 February 2023 diff hist +11‎ Coppersmith–Winograd algorithm (Matrix Multiplication Matrix Product) ‎No edit summary Tag: Manual revert
• 11:1311:13, 15 February 2023 diff hist −38‎ Strassen's algorithm (Matrix Multiplication Matrix Product) ‎No edit summary Tags: Manual revert Reverted
• 11:1311:13, 15 February 2023 diff hist −11‎ Coppersmith–Winograd algorithm (Matrix Multiplication Matrix Product) ‎No edit summary Tags: Manual revert Reverted
• 11:1311:13, 15 February 2023 diff hist +38‎ Strassen's algorithm (Matrix Multiplication Matrix Product) ‎No edit summary Tags: Manual revert Reverted
• 11:1211:12, 15 February 2023 diff hist +21‎ Serang (Subset Sum The Subset-Sum Problem) ‎No edit summary Tags: Manual revert Reverted
• 11:0911:09, 15 February 2023 diff hist +282,467‎ N List:Algorithms ‎ Created page with "{| class="wikitable sortable" style="text-align:center;" width="100%" ! Family !! Name !! Year !! Time Complexity !! Space Complexity |- | style="text-align:left;" | Approximate OBST || style="text-align:left;" | Melhorn's Approximation algorithm (Approximate OBST Optimal Binary Search Trees) || 1975 || $O(n)$ || $O(n)$ |- | style="text-align:left;" | Approximate OBST || style="text-align:left;" | Karpinski (Appro..."
• 10:5710:57, 15 February 2023 diff hist −3,740‎ Main Page ‎No edit summary current
• 10:5710:57, 15 February 2023 diff hist 0‎ File:F4.png ‎ Admin uploaded a new version of File:F4.png current
• 10:5710:57, 15 February 2023 diff hist 0‎ N File:Banner.png ‎No edit summary current
• 10:5710:57, 15 February 2023 diff hist 0‎ N File:H4.png ‎No edit summary current
• 10:5710:57, 15 February 2023 diff hist 0‎ File:F9.png ‎ Admin uploaded a new version of File:F9.png current
• 10:5710:57, 15 February 2023 diff hist 0‎ N File:H2.png ‎No edit summary current
• 10:5710:57, 15 February 2023 diff hist 0‎ File:F3.png ‎ Admin uploaded a new version of File:F3.png current
• 10:5710:57, 15 February 2023 diff hist 0‎ File:F2.png ‎ Admin uploaded a new version of File:F2.png current
• 10:5710:57, 15 February 2023 diff hist 0‎ N File:D4.png ‎No edit summary current
• 10:5710:57, 15 February 2023 diff hist 0‎ File:F5.png ‎ Admin uploaded a new version of File:F5.png current
• 10:5710:57, 15 February 2023 diff hist 0‎ File:F7.png ‎ Admin uploaded a new version of File:F7.png current
• 10:5710:57, 15 February 2023 diff hist 0‎ N File:D3.png ‎No edit summary current
• 10:5710:57, 15 February 2023 diff hist 0‎ N File:D1.png ‎No edit summary current
• 10:5710:57, 15 February 2023 diff hist 0‎ N File:H1.png ‎No edit summary current
• 10:5710:57, 15 February 2023 diff hist 0‎ N File:D5.png ‎No edit summary current
• 10:5710:57, 15 February 2023 diff hist 0‎ File:F8.png ‎ Admin uploaded a new version of File:F8.png current
• 10:5710:57, 15 February 2023 diff hist 0‎ N File:Download.png ‎No edit summary current
• 10:5710:57, 15 February 2023 diff hist 0‎ N File:D7.png ‎No edit summary current
• 10:5710:57, 15 February 2023 diff hist 0‎ N File:D2.png ‎No edit summary current
• 10:5610:56, 15 February 2023 diff hist 0‎ N File:D10.png ‎No edit summary current
• 10:5610:56, 15 February 2023 diff hist 0‎ N File:D6.png ‎No edit summary current
• 10:5610:56, 15 February 2023 diff hist 0‎ N File:D8.png ‎No edit summary current
• 10:5610:56, 15 February 2023 diff hist 0‎ File:F1.png ‎ Admin uploaded a new version of File:F1.png current
• 10:5610:56, 15 February 2023 diff hist 0‎ N File:H3.png ‎No edit summary current
• 10:5610:56, 15 February 2023 diff hist 0‎ File:F6.png ‎ Admin uploaded a new version of File:F6.png current
• 10:5610:56, 15 February 2023 diff hist 0‎ N File:D9.png ‎No edit summary current
• 10:5510:55, 15 February 2023 diff hist −92‎ Reduction from MAX-CNF-SAT to st-Maximum Flow ‎No edit summary Tag: Reverted
• 10:5510:55, 15 February 2023 diff hist +480‎ N Reduction from MAX-CNF-SAT to Maximum Local Edge Connectivity ‎ 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..." current
• 10:5510:55, 15 February 2023 diff hist +92‎ Reduction from MAX-CNF-SAT to All-Pairs Maximum Flow ‎No edit summary Tag: Reverted
• 10:5510:55, 15 February 2023 diff hist +510‎ N Reduction from MAX-CNF-SAT to All-Pairs Maximum Flow ‎ 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:5510:55, 15 February 2023 diff hist +676‎ N Reduction from Directed, Weighted APSP to Dynamic Bipartite Maximum-Weight Matching ‎ 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..." current
• 10:5510:55, 15 February 2023 diff hist +595‎ N Reduction from MAX-CNF-SAT to st-Maximum Flow ‎ 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:5510:55, 15 February 2023 diff hist +661‎ N Reduction from Directed, Weighted APSP to Dynamic $st$-Shortest Path ‎ 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..." current
• 10:5510:55, 15 February 2023 diff hist +767‎ N Reduction from Triangle Detection to Dynamic Bipartite Maximum-Weight Matching ‎ 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..." current
• 10:5510:55, 15 February 2023 diff hist +755‎ N Reduction from Triangle Detection to Strong Connectivity (dynamic) ‎ 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..." current
• 10:5510:55, 15 February 2023 diff hist +791‎ N Reduction from Triangle Detection to Dynamic st-Reach ‎ 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..." current
• 10:5510:55, 15 February 2023 diff hist +676‎ N Reduction from CNF-SAT to Dynamic 4/3-Diameter ‎ 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..." current
• 10:5510:55, 15 February 2023 diff hist +672‎ N Reduction from CNF-SAT to Dynamic ST-Reach ‎ 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..." current
• 10:5510:55, 15 February 2023 diff hist +699‎ N Reduction from CNF-SAT to Dynamic Connected Subgraph ‎ 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..." current
• 10:5510:55, 15 February 2023 diff hist +687‎ N Reduction from CNF-SAT to Dynamic MaxSCC ‎ 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..." current
• 10:5510:55, 15 February 2023 diff hist +677‎ N Reduction from CNF-SAT to ‎ 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..." current
• 10:5510:55, 15 February 2023 diff hist +676‎ N Reduction from CNF-SAT to SC2 ‎ 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..." current
• 10:5510:55, 15 February 2023 diff hist +635‎ N Reduction from Min-Weight k-Clique to Minimum Weight k-Cycle ‎ 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..." current