User contributions for Admin

15 February 2023

• 11:1911:19, 15 February 2023 diff hist +481‎ N Reduction from BMM to ap-reach ‎ Created page with "FROM: BMM TO: ap-reach == Description == == Implications == assume: BMM<br/>then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity problems. arXiv preprint arXiv:1703.01638. https://arxiv.org/pdf/1703.016..." current
• 11:1911:19, 15 February 2023 diff hist +505‎ N Reduction from BMM to 1-sensitive incremental ss-reach ‎ Created page with "FROM: BMM TO: 1-sensitive incremental ss-reach == Description == == Implications == assume: BMM<br/>then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity problems. arXiv preprint arXiv:1703.01638. https:..." current
• 11:1911:19, 15 February 2023 diff hist +505‎ N Reduction from BMM to 2-sensitive incremental st-reach ‎ Created page with "FROM: BMM TO: 2-sensitive incremental st-reach == Description == == Implications == assume: BMM<br/>then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity problems. arXiv preprint arXiv:1703.01638. https:..." current
• 11:1911:19, 15 February 2023 diff hist +90‎ Reduction from Triangle Collection* to dynamic 4/3-Diameter ‎No edit summary Tag: Reverted
• 11:1911:19, 15 February 2023 diff hist −134‎ Reduction from Triangle Collection* to dynamic 4/3-Diameter ‎No edit summary
• 11:1911:19, 15 February 2023 diff hist +710‎ N Reduction from Triangle Collection* to dynamic 4/3-Diameter ‎ Created page with "FROM: Triangle Collection* TO: dynamic 4/3-Diameter == Description == == Implications == assume: SETH or {3}SUM Hypothesis or APSP Hypothesis<br/>then: there exists no incremental (or decremental) algorithm that approximates the diameter of unweighted graph within a factor of ${4}/{3}-\epsilon$ running in amortized time $O(n^{1/{2}-\epsilon'})$ for any $\epsilon,\epsilon' > {0}$. Furthermore, if we allow node insertions in the incremental case the bound is..."
• 11:1911:19, 15 February 2023 diff hist +548‎ N Reduction from OuMV to dynamic st-Maximum Flow ‎ Created page with "FROM: OuMV TO: dynamic st-Maximum Flow == Description == == Implications == assume: OMv<br/>then: there is no algorithm for solving incremental (or decremental) st-max-flow on unweifghted directed graphs or weighted undirected graphs on $n$ nodes with amortized time $O(n^{1-\epsilon})$ per operation for any $\epsilon > {0}$ == Year == 2016 == Reference == Dahlgaard, S. (2016). On the hardness of partially dynamic graph problems and connections to dia..." current
• 11:1911:19, 15 February 2023 diff hist +551‎ N Reduction from CNF-SAT to dynamic st-Maximum Flow ‎ Created page with "FROM: CNF-SAT TO: dynamic st-Maximum Flow == Description == == Implications == assume: SETH<br/>then: there is no algorithm for solving incremental (or decremental) st-max-flow on a weighted and directed graph with $n$ nodes and $\tilde{O}(n)$ edges with amortized time $O(m^{1-\epsilon})$ per operation for any $\epsilon > {0}$ == Year == 2016 == Reference == Dahlgaard, S. (2016). On the hardness of partially dynamic graph problems and connections to..." current
• 11:1911:19, 15 February 2023 diff hist +550‎ N Reduction from OuMv to Bipartite Graph MCM ‎ Created page with "FROM: OuMv TO: Bipartite Graph MCM == Description == == Implications == assume: OMv<br/>then: there is no algorithm for solving incremental (or decremental) maximum cardinality bipartite matching with amortized time $O(n^{1-\epsilon})$ per insertion (or deletion) and $O(n^{2-\epsilon})$ time per query for any $\epsilon > {0}$ == Year == 2016 == Reference == Dahlgaard, S. (2016). On the hardness of partially dynamic graph problems and connections to d..." current
• 11:1911:19, 15 February 2023 diff hist −92‎ Reduction from MAX-CNF-SAT to st-Maximum Flow ‎No edit summary current Tag: Manual revert
• 11:1911:19, 15 February 2023 diff hist −92‎ Reduction from MAX-CNF-SAT to All-Pairs Maximum Flow ‎No edit summary Tags: Manual revert Reverted
• 11:1911:19, 15 February 2023 diff hist +92‎ Reduction from MAX-CNF-SAT to st-Maximum Flow ‎No edit summary Tags: Manual revert Reverted
• 11:1911:19, 15 February 2023 diff hist −26‎ Reduction from CNF-SAT to Approximate Reach Centrality ‎No edit summary Tags: Manual revert Reverted
• 11:1911:19, 15 February 2023 diff hist +26‎ Reduction from CNF-SAT to Approximate Reach Centrality ‎No edit summary Tags: Manual revert Reverted
• 11:1811:18, 15 February 2023 diff hist +251‎ Reduction from Reach Centrality to Diameter ‎No edit summary Tags: Manual revert Reverted
• 11:1811:18, 15 February 2023 diff hist −251‎ Reduction from Reach Centrality to Diameter ‎No edit summary Tags: Manual revert Reverted
• 11:1811:18, 15 February 2023 diff hist −49‎ Reduction from Matrix Product to Negative Triangle Detection ‎No edit summary Tags: Manual revert Reverted
• 11:1811:18, 15 February 2023 diff hist +52‎ Reduction from Matrix Product to Negative Triangle Detection ‎No edit summary Tags: Manual revert Reverted
• 11:1811:18, 15 February 2023 diff hist +7‎ Reduction from Matrix Product to Negative Triangle Detection ‎No edit summary Tags: Manual revert Reverted
• 11:1811:18, 15 February 2023 diff hist −10‎ Reduction from Matrix Product to Negative Triangle Detection ‎No edit summary Tags: Manual revert Reverted
• 11:1811:18, 15 February 2023 diff hist +455‎ N Reduction from GeomBase to Visibility Between Segments ‎ Created page with "FROM: GeomBase TO: Visibility Between Segments == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2" current
• 11:1811:18, 15 February 2023 diff hist +450‎ N Reduction from Strips Cover Box to Point Covering ‎ Created page with "FROM: Strips Cover Box TO: Point Covering == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2" current
• 11:1811:18, 15 February 2023 diff hist +460‎ N Reduction from Triangles Cover Triangle to Triangle Measure ‎ Created page with "FROM: Triangles Cover Triangle TO: Triangle Measure == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2" current
• 11:1811:18, 15 February 2023 diff hist +457‎ N Reduction from Hole in Union to Triangles Cover Triangle ‎ Created page with "FROM: Hole in Union TO: Triangles Cover Triangle == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2" current
• 11:1811:18, 15 February 2023 diff hist +457‎ N Reduction from Triangles Cover Triangle to Hole in Union ‎ Created page with "FROM: Triangles Cover Triangle TO: Hole in Union == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2" current
• 11:1811:18, 15 February 2023 diff hist +460‎ N Reduction from Strips Cover Box to Triangles Cover Triangle ‎ Created page with "FROM: Strips Cover Box TO: Triangles Cover Triangle == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2" current
• 11:1811:18, 15 February 2023 diff hist +444‎ N Reduction from GeomBase to Strips Cover Box ‎ Created page with "FROM: GeomBase TO: Strips Cover Box == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2" current
• 11:1811:18, 15 February 2023 diff hist +438‎ N Reduction from GeomBase to Separator2 ‎ Created page with "FROM: GeomBase TO: Separator2 == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2" current
• 11:1811:18, 15 February 2023 diff hist +438‎ N Reduction from GeomBase to Separator1 ‎ Created page with "FROM: GeomBase TO: Separator1 == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2" current
• 11:1811:18, 15 February 2023 diff hist +440‎ N Reduction from 3SUM to 3 Points on Line ‎ Created page with "FROM: 3SUM TO: 3 Points on Line == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2" current
• 11:1811:18, 15 February 2023 diff hist +452‎ N Reduction from 3 Points on Line to Point on 3 Lines ‎ Created page with "FROM: 3 Points on Line TO: Point on 3 Lines == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2" current
• 11:1811:18, 15 February 2023 diff hist +433‎ N Reduction from 3SUM' to GeomBase ‎ Created page with "FROM: 3SUM' TO: GeomBase == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2" current
• 11:1811:18, 15 February 2023 diff hist +433‎ N Reduction from GeomBase to 3SUM' ‎ Created page with "FROM: GeomBase TO: 3SUM' == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2" current
• 11:1811:18, 15 February 2023 diff hist +429‎ N Reduction from 3SUM' to 3SUM ‎ Created page with "FROM: 3SUM' TO: 3SUM == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2" current
• 11:1811:18, 15 February 2023 diff hist +332‎ N Reduction from OV to Partial Match ‎ Created page with "FROM: OV TO: Partial Match == Description == == Implications == If: to-time: $n^{2-\epsilon}*poly(d)$ for some $\epsilon > {0}$<br/>Then: from-time: $n^{2-\epsilon'}*poly(d)$ for some $\epsilon' > {0}$ == Year == 2020 == Reference == 6.S078 Lecture 6 https://people.csail.mit.edu/virgi/6.s078/lecture6-post.txt" current
• 11:1811:18, 15 February 2023 diff hist +429‎ N Reduction from 3SUM to 3SUM' ‎ Created page with "FROM: 3SUM TO: 3SUM' == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2" current
• 11:1811:18, 15 February 2023 diff hist +332‎ N Reduction from Partial Match to OV ‎ Created page with "FROM: Partial Match TO: OV == Description == == Implications == If: to-time: $n^{2-\epsilon}*poly(d)$ for some $\epsilon > {0}$<br/>Then: from-time: $n^{2-\epsilon'}*poly(d)$ for some $\epsilon' > {0}$ == Year == 2020 == Reference == 6.S078 Lecture 6 https://people.csail.mit.edu/virgi/6.s078/lecture6-post.txt" current
• 11:1811:18, 15 February 2023 diff hist +300‎ N Reduction from UOV to Longest Common Subsequence ‎ Created page with "FROM: UOV TO: Longest Common Subsequence == Description == == Implications == If: to-time: $O((nm)^{({1}-\epsilon)})$, where $|x| = O(nd)$ and $|y| = O(md)$<br/>Then: from-time: $O((nm)^{({1}-\epsilon/{2})})$ == Year == 2015 == Reference == https://arxiv.org/pdf/1502.01063.pdf" current
• 11:1811:18, 15 February 2023 diff hist +495‎ N Reduction from CNF-SAT to Frechet Distance ‎ Created page with "FROM: CNF-SAT TO: Frechet Distance == Description == == Implications == If: to-time: $O({2}^{({2}-\epsilon)}$ for any $\epsilon > {0}$<br/>Then: from-time: $O({2}^{({1}-\delta/{2})N}$ where $N$ is s.t there are $n=\tilde{O}({2}^{N/2})$ vertices on each curve == Year == 2014 == Reference == Karl Bringmann, Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails https://people.mpi-inf.mpg.de/~kbringm..." current
• 11:1811:18, 15 February 2023 diff hist +294‎ N Reduction from UOV to Dynamic Time Warping ‎ Created page with "FROM: UOV TO: Dynamic Time Warping == Description == == Implications == If: to-time: $O((nm)^{({1}-\epsilon)})$, where $|x| = O(nd)$ and $|y| = O(md)$<br/>Then: from-time: $O((nm)^{({1}-\epsilon/{2})})$ == Year == 2015 == Reference == https://arxiv.org/pdf/1502.01063.pdf" current
• 11:1811:18, 15 February 2023 diff hist +506‎ N Reduction from OV to Diameter 2 vs 3 ‎ Created page with "FROM: OV TO: Diameter 2 vs 3 == Description == == Implications == If: to-time: $O(N^{({2}-\epsilon)})$ where $N = nd$ and $V,E = O(n)$<br/>Then: from-time: $O((nd)^{({2}-\epsilon)}) \leq n^{({2}-\epsilon)} poly(d)$ where {2} sets of $n$ $d$-dimensional vectors == 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://peop..." current
• 11:1811:18, 15 February 2023 diff hist +535‎ N Reduction from OV to Edit Distance ‎ Created page with "FROM: OV TO: Edit Distance == Description == == Implications == If: to-time: $O(n^{({2}-\epsilon)})$ where $n$ is length of sequence<br/>Then: from-time: $O(d^(O({1})*(N)^{({2}-\epsilon)})$ where ${2}$ sets of $n$ $d$-dimensional vectors == Year == 2014 == Reference == Backurs, Arturs, and Piotr Indyk. "Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)." Proceedings of the forty-seventh annual ACM symposium on Theo..."
• 11:1811:18, 15 February 2023 diff hist +469‎ N Reduction from 3-OV to Diameter 3 vs 7 ‎ Created page with "FROM: 3-OV TO: Diameter 3 vs 7 == Description == == Implications == If: to-time: $O(N^{({3}/{2}-\epsilon)}$ where $N=n^{2} d^{2}$ and $\epsilon > {0}$<br/>Then: from-time: $n^{3-{2}\epsilon} poly(d)$ == Year == 2018 == Reference == Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein. Towards tight approximation bounds for graph diameter and eccentricities. https://dl.acm.org/doi/pdf/10.1145/3188745.3188950" current
• 11:1811:18, 15 February 2023 diff hist +466‎ N Reduction from CNF-SAT to k-OV ‎ Created page with "FROM: CNF-SAT TO: k-OV == Description == == Implications == If: to-time: $N^{(k-\epsilon)} poly(m)$ where $m$-dimensional vectors, $k$-OV, $N$ vectors per set<br/>Then: from-time: ${2}^{(n-\epsilon')} \poly(m)$ where $\epsilon' = \epsilon/k > {0}$, $n$ variables, $m$ clauses == Year == 2005 == Reference == Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357–365, 2005." current
• 11:1811:18, 15 February 2023 diff hist +350‎ N Fagin (4NF Decomposition for Functional and Multivalued Dependency Sets 4NF Decomposition) ‎ Created page with "== Time Complexity == exponential == Space Complexity == exponential words (https://link.springer.com/article/10.1007/BF01934180) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1977 == Reference == https://dl.acm.org/doi/abs/10.1145/320557.320571" current
• 11:1811:18, 15 February 2023 diff hist +285‎ N Sciore (4NF Decomposition for Conflict-Free Dependency Sets 4NF Decomposition) ‎ Created page with "== Time Complexity == poly-time == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1981 == Reference == https://dl.acm.org/doi/abs/10.1145/582318.582337" current
• 11:1811:18, 15 February 2023 diff hist +360‎ N Grahne and Räihä (4NF Decomposition for Functional and Multivalued Dependency Sets 4NF Decomposition) ‎ Created page with "== Time Complexity == exponential == Space Complexity == exponential words (https://link.springer.com/article/10.1007/BF01934180) == Description == Synthesis Algorithm == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1983 == Reference == https://www.vldb.org/conf/1983/P186.PDF" current
• 11:1811:18, 15 February 2023 diff hist +387‎ N Lien (4NF Decomposition for Conflict-Free Dependency Sets 4NF Decomposition) ‎ Created page with "== Time Complexity == $O(k^{2} n^{2})$ == Space Complexity == $O(k^{2})$ words (Derived: Uses an auxiliary array of size $k \times k$) == Description == Multiway Decomposition Algorithm == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1982 == Reference == https://dl.acm.org/doi/abs/10.1145/319540.319546" current
• 11:1811:18, 15 February 2023 diff hist +307‎ N Global Newton Method (n player games Nash Equilibria) ‎ Created page with "== Time Complexity == Unknown == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 2008 == Reference == https://www.sciencedirect.com/science/article/pii/S0022053108000811" current
• 11:1811:18, 15 February 2023 diff hist +292‎ N Mixed Integer Programming (n player games Nash Equilibria) ‎ Created page with "== Time Complexity == Unknown == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 2005 == Reference == https://www.aaai.org/Papers/AAAI/2005/AAAI05-078.pdf" current