All public logs
Jump to navigation
Jump to search
Combined display of all available logs of Algorithm Wiki. You can narrow down the view by selecting a log type, the username (case-sensitive), or the affected page (also case-sensitive).
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)- 10:57, 15 February 2023 Admin talk contribs uploaded a new version of File:F4.png
- 10:57, 15 February 2023 Admin talk contribs created page File:Banner.png
- 10:57, 15 February 2023 Admin talk contribs uploaded File:Banner.png
- 10:57, 15 February 2023 Admin talk contribs created page File:H4.png
- 10:57, 15 February 2023 Admin talk contribs uploaded File:H4.png
- 10:57, 15 February 2023 Admin talk contribs uploaded a new version of File:F9.png
- 10:57, 15 February 2023 Admin talk contribs created page File:H2.png
- 10:57, 15 February 2023 Admin talk contribs uploaded File:H2.png
- 10:57, 15 February 2023 Admin talk contribs uploaded a new version of File:F3.png
- 10:57, 15 February 2023 Admin talk contribs uploaded a new version of File:F2.png
- 10:57, 15 February 2023 Admin talk contribs created page File:D4.png
- 10:57, 15 February 2023 Admin talk contribs uploaded File:D4.png
- 10:57, 15 February 2023 Admin talk contribs uploaded a new version of File:F5.png
- 10:57, 15 February 2023 Admin talk contribs uploaded a new version of File:F7.png
- 10:57, 15 February 2023 Admin talk contribs created page File:D3.png
- 10:57, 15 February 2023 Admin talk contribs uploaded File:D3.png
- 10:57, 15 February 2023 Admin talk contribs created page File:D1.png
- 10:57, 15 February 2023 Admin talk contribs uploaded File:D1.png
- 10:57, 15 February 2023 Admin talk contribs created page File:H1.png
- 10:57, 15 February 2023 Admin talk contribs uploaded File:H1.png
- 10:57, 15 February 2023 Admin talk contribs created page File:D5.png
- 10:57, 15 February 2023 Admin talk contribs uploaded File:D5.png
- 10:57, 15 February 2023 Admin talk contribs uploaded a new version of File:F8.png
- 10:57, 15 February 2023 Admin talk contribs created page File:Download.png
- 10:57, 15 February 2023 Admin talk contribs uploaded File:Download.png
- 10:57, 15 February 2023 Admin talk contribs created page File:D7.png
- 10:57, 15 February 2023 Admin talk contribs uploaded File:D7.png
- 10:57, 15 February 2023 Admin talk contribs created page File:D2.png
- 10:57, 15 February 2023 Admin talk contribs uploaded File:D2.png
- 10:56, 15 February 2023 Admin talk contribs created page File:D10.png
- 10:56, 15 February 2023 Admin talk contribs uploaded File:D10.png
- 10:56, 15 February 2023 Admin talk contribs created page File:D6.png
- 10:56, 15 February 2023 Admin talk contribs uploaded File:D6.png
- 10:56, 15 February 2023 Admin talk contribs created page File:D8.png
- 10:56, 15 February 2023 Admin talk contribs uploaded File:D8.png
- 10:56, 15 February 2023 Admin talk contribs uploaded a new version of File:F1.png
- 10:56, 15 February 2023 Admin talk contribs created page File:H3.png
- 10:56, 15 February 2023 Admin talk contribs uploaded File:H3.png
- 10:56, 15 February 2023 Admin talk contribs uploaded a new version of File:F6.png
- 10:56, 15 February 2023 Admin talk contribs created page File:D9.png
- 10:56, 15 February 2023 Admin talk contribs uploaded File:D9.png
- 10:55, 15 February 2023 Admin talk contribs created page 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...")
- 10:55, 15 February 2023 Admin talk contribs created page 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:55, 15 February 2023 Admin talk contribs created page 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...")
- 10:55, 15 February 2023 Admin talk contribs created page 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:55, 15 February 2023 Admin talk contribs created page 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...")
- 10:55, 15 February 2023 Admin talk contribs created page 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...")
- 10:55, 15 February 2023 Admin talk contribs created page 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...")
- 10:55, 15 February 2023 Admin talk contribs created page 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...")
- 10:55, 15 February 2023 Admin talk contribs created page 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...")
