New pages

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

• 11:19, 15 February 2023 ‎Reduction from OV to Generalized Büchi Games (hist | edit) ‎[678 bytes] ‎Admin (talk | contribs) (Created page with "FROM: OV TO: Generalized Büchi Games == Description == == Implications == assume: OVH<br/>then: there is no $O(m^{2-\epsilon})$ or $O(\min_{1 \leq i \leq k} b_i \cdot (k \cdot m)^{1-\epsilon})$-time algorithm (for any $\epsilon > {0}$ for generalized Büchi games. In particular there is no such algorithm for deciding whether the winning set is non-empty or deciding whether a specifc vertex is in the winning set. == Year == 2016 == Reference == Chat...")
• 11:19, 15 February 2023 ‎Reduction from Triangle Detection to Disjunctive coBüchi Objectives (hist | edit) ‎[692 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Triangle Detection TO: Disjunctive coBüchi Objectives == Description == == Implications == assume: Strong Triangle<br/>then: there is no combinatorial $O(n^{3-\epsilon})$ or $O((k\cdot n^{2})^{1-\epsilon})$-time algorithm for any $epsilon > {0}$ for generalized Büchi games. In particular, there is no such algorithm deciding whether the winning set is non-empty or deciding whether a specific vertex is in the winning set. == Year == 2016 == Refer...")
• 11:19, 15 February 2023 ‎Reduction from OV to Largest Common Subtree (hist | edit) ‎[563 bytes] ‎Admin (talk | contribs) (Created page with "FROM: OV TO: Largest Common Subtree == Description == == Implications == assume: OVH<br/>then: for all constants $d \geq {2}$, target on two rooted trees of size at most $n$, degree $d$, and height $h \leq \log_d n + O(\log \log n)$ cannot be solved in truly subquadtratic $O(n^{2-\epsilon})$ time == Year == 2018 == Reference == Abboud, A., Backurs, A., Hansen, T. D., Vassilevska Williams, V., & Zamir, O. (2018). Subtree isomorphism revisited. ACM Tra...")
• 11:19, 15 February 2023 ‎Reduction from k-SAT to Subset Sum (hist | edit) ‎[544 bytes] ‎Admin (talk | contribs) (Created page with "FROM: k-SAT TO: Subset Sum == Description == == Implications == assume: SETH<br/>then: for any $\epsilon > {0}$ there exists a $\delta > {0}$ such that Subset Sum is not in time $O(T^{1-\epsilon}{2}^{\delta n})$, and $k$-Sum is not in time $O(T^{1-\epsilon}n^{\delta k})$ == Year == 2022 == Reference == Abboud, A., Bringmann, K., Hermelin, D., & Shabtay, D. (2022). SETH-based lower bounds for subset sum and bicriteria path. ACM Transactions on Algorit...")
• 11:19, 15 February 2023 ‎Reduction from OV to Subtree Isomorphism (hist | edit) ‎[557 bytes] ‎Admin (talk | contribs) (Created page with "FROM: OV TO: Subtree Isomorphism == Description == == Implications == assume: OVH<br/>then: for all $d \geq {2}$, target on two rooted unordered trees of size $O(n)$, degree $d$, and height $h \leq {2}\log_d n + O(\log \log n)$ cannot be solved in truly subquadratic $O(n^{2-\epsilon})$ time == Year == 2018 == Reference == Abboud, A., Backurs, A., Hansen, T. D., Vassilevska Williams, V., & Zamir, O. (2018). Subtree isomorphism revisited. ACM Transacti...")
• 11:19, 15 February 2023 ‎Reduction from k-Clique to RNA Folding (hist | edit) ‎[590 bytes] ‎Admin (talk | contribs) (Created page with "FROM: k-Clique TO: RNA Folding == Description == == Implications == assume: k-Clique Hypothesis<br/>then: there is no $O(N^{\omega-\epsilon}) time algorithm for target for any $\epsilon > {0}$ == Year == 2017 == Reference == Abboud, A., Backurs, A., Bringmann, K., & Künnemann, M. (2017, October). Fine-grained complexity of analyzing compressed data: Quantifying improvements over decompress-and-solve. In 2017 IEEE 58th Annual Symposium on Foundations...")
• 11:19, 15 February 2023 ‎Reduction from k-Clique to CFG Recognition (hist | edit) ‎[594 bytes] ‎Admin (talk | contribs) (Created page with "FROM: k-Clique TO: CFG Recognition == Description == == Implications == assume: k-Clique Hypothesis<br/>then: there is no $O(N^{\omega-\epsilon}) time algorithm for target for any $\epsilon > {0}$ == Year == 2017 == Reference == Abboud, A., Backurs, A., Bringmann, K., & Künnemann, M. (2017, October). Fine-grained complexity of analyzing compressed data: Quantifying improvements over decompress-and-solve. In 2017 IEEE 58th Annual Symposium on Foundat...")
• 11:19, 15 February 2023 ‎Reduction from OV to Bichromatic Hamming Close Pair (hist | edit) ‎[525 bytes] ‎Admin (talk | contribs) (Created page with "FROM: OV TO: Bichromatic Hamming Close Pair == Description == == Implications == assume: OVH<br/>then: there is no algorithm to solve target in time $O({2}^{o(d)}n^{2-\epsilon})$ on a set of $n$ points in $\{0,{1}\}^{c\log n}$ == Year == 2015 == Reference == Alman, J., & Williams, R. (2015, October). Probabilistic polynomials and hamming nearest neighbors. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (pp. 136-150). IEEE. htt...")
• 11:19, 15 February 2023 ‎Reduction from CNF-SAT to sensitive incremental ST-Reach (hist | edit) ‎[590 bytes] ‎Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: sensitive incremental ST-Reach == Description == == Implications == assume: SETH<br/>then: let $\epsilon > {0}$, $t \in \mathbb{N}$, there exists no algorithm for target with preprocessing time $O(n^t)$, update time $u(n)$ and query time $q(n)$, such that $max\{u(n),q(n)\}=O(n^{1-\epsilon})$ with constant sensitivity $K(\epsilon,t)$ == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Co...")
• 11:19, 15 February 2023 ‎Reduction from CNF-SAT to constant sensitivity (4/3)-approximate incremental diameter (hist | edit) ‎[619 bytes] ‎Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: constant sensitivity (4/3)-approximate incremental diameter == Description == == Implications == assume: SETH<br/>then: let $\epsilon > {0}$, $t \in \mathbb{N}$, there exists no algorithm for target with preprocessing time $O(n^t)$, update time $u(n)$ and query time $q(n)$, such that $max\{u(n),q(n)\}=O(n^{1-\epsilon})$ with constant sensitivity $K(\epsilon,t)$ == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S.,...")
• 11:19, 15 February 2023 ‎Reduction from Directed, Weighted APSP to 1-sensitive decremental diameter (hist | edit) ‎[545 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Directed, Weighted APSP TO: 1-sensitive decremental diameter == Description == == Implications == assume: APSP Hypothesis<br/>then: target cannot be solved with preprocessing time $O(n^{3-\epsilon})$ and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ in undirected weighted graphs == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity problems....")
• 11:19, 15 February 2023 ‎Reduction from CNF-SAT to sensitive incremental (hist | edit) ‎[586 bytes] ‎Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: sensitive incremental #SSR == Description == == Implications == assume: SETH<br/>then: let $\epsilon > {0}$, $t \in \mathbb{N}$, there exists no algorithm for target with preprocessing time $O(n^t)$, update time $u(n)$ and query time $q(n)$, such that $max\{u(n),q(n)\}=O(n^{1-\epsilon})$ with constant sensitivity $K(\epsilon,t)$ == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Condit...")
• 11:19, 15 February 2023 ‎Reduction from Directed, Weighted APSP to 2-sensitive decremental st-shortest paths (hist | edit) ‎[554 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Directed, Weighted APSP TO: 2-sensitive decremental st-shortest paths == Description == == Implications == assume: APSP Hypothesis<br/>then: target cannot be solved with preprocessing time $O(n^{3-\epsilon})$ and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ in undirected weighted graphs == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity p...")
• 11:19, 15 February 2023 ‎Reduction from Replacement Paths Problem (RPP) to 1-sensitive decremental st-shortest paths (hist | edit) ‎[560 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Replacement Paths Problem (RPP) TO: 1-sensitive decremental st-shortest paths == Description == == Implications == assume: APSP Hypothesis<br/>then: target cannot be solved with preprocessing time $O(n^{3-\epsilon})$ and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ in directed weighted graphs == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensiti...")
• 11:19, 15 February 2023 ‎Reduction from BMM to 1-sensitive decremental st-shortest paths (hist | edit) ‎[547 bytes] ‎Admin (talk | contribs) (Created page with "FROM: BMM TO: 1-sensitive decremental st-shortest paths == Description == == Implications == assume: BMM<br/>then: for directed unweighted graphs with $n$ vertices and $m \geq n$ edges require either $m^{1-o({1})}\sqrt{n}$ preprocessing time or $m^{1-o({1})}/\sqrt{n}$ query time for every function $m$ of $n$ == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity problems...")
• 11:19, 15 February 2023 ‎Reduction from BMM to 1-sensitive (4/3)-approximate decremental eccentricity (hist | edit) ‎[527 bytes] ‎Admin (talk | contribs) (Created page with "FROM: BMM TO: 1-sensitive (4/3)-approximate decremental eccentricity == 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 arX...")
• 11:19, 15 February 2023 ‎Reduction from BMM to 1-sensitive (4/3)-approximate decremental diameter (hist | edit) ‎[555 bytes] ‎Admin (talk | contribs) (Created page with "FROM: BMM TO: 1-sensitive (4/3)-approximate decremental diameter == 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}$ in undirected unweighted graphs == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity...")
• 11:19, 15 February 2023 ‎Reduction from BMM to (5/3)-approximate ap-shortest paths (hist | edit) ‎[508 bytes] ‎Admin (talk | contribs) (Created page with "FROM: BMM TO: (5/3)-approximate ap-shortest paths == 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. htt...")
• 11:19, 15 February 2023 ‎Reduction from BMM to 1-sensitive (3/2)-approximate ss-shortest paths (hist | edit) ‎[552 bytes] ‎Admin (talk | contribs) (Created page with "FROM: BMM TO: 1-sensitive (3/2)-approximate ss-shortest paths == 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}$ in undirected unweighted graphs == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity pro...")
• 11:19, 15 February 2023 ‎Reduction from BMM to 2-sensitive (7/5)-approximate st-shortest paths (hist | edit) ‎[552 bytes] ‎Admin (talk | contribs) (Created page with "FROM: BMM TO: 2-sensitive (7/5)-approximate st-shortest paths == 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}$ in undirected unweighted graphs == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity pro...")
• 11:19, 15 February 2023 ‎Reduction from BMM to ap-reach (hist | edit) ‎[481 bytes] ‎Admin (talk | contribs) (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...")
• 11:19, 15 February 2023 ‎Reduction from BMM to 2-sensitive incremental st-reach (hist | edit) ‎[505 bytes] ‎Admin (talk | contribs) (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:...")
• 11:19, 15 February 2023 ‎Reduction from BMM to 1-sensitive incremental ss-reach (hist | edit) ‎[505 bytes] ‎Admin (talk | contribs) (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:...")
• 11:19, 15 February 2023 ‎Reduction from Triangle Collection* to dynamic 4/3-Diameter (hist | edit) ‎[666 bytes] ‎Admin (talk | contribs) (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:19, 15 February 2023 ‎Reduction from OuMV to dynamic st-Maximum Flow (hist | edit) ‎[548 bytes] ‎Admin (talk | contribs) (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...")
• 11:19, 15 February 2023 ‎Reduction from CNF-SAT to dynamic st-Maximum Flow (hist | edit) ‎[551 bytes] ‎Admin (talk | contribs) (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...")
• 11:19, 15 February 2023 ‎Reduction from OuMv to Bipartite Graph MCM (hist | edit) ‎[550 bytes] ‎Admin (talk | contribs) (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...")
• 11:18, 15 February 2023 ‎Reduction from GeomBase to Visibility Between Segments (hist | edit) ‎[455 bytes] ‎Admin (talk | contribs) (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")
• 11:18, 15 February 2023 ‎Reduction from Strips Cover Box to Point Covering (hist | edit) ‎[450 bytes] ‎Admin (talk | contribs) (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")
• 11:18, 15 February 2023 ‎Reduction from Triangles Cover Triangle to Triangle Measure (hist | edit) ‎[460 bytes] ‎Admin (talk | contribs) (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")
• 11:18, 15 February 2023 ‎Reduction from Hole in Union to Triangles Cover Triangle (hist | edit) ‎[457 bytes] ‎Admin (talk | contribs) (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")
• 11:18, 15 February 2023 ‎Reduction from Strips Cover Box to Triangles Cover Triangle (hist | edit) ‎[460 bytes] ‎Admin (talk | contribs) (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")
• 11:18, 15 February 2023 ‎Reduction from Triangles Cover Triangle to Hole in Union (hist | edit) ‎[457 bytes] ‎Admin (talk | contribs) (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")
• 11:18, 15 February 2023 ‎Reduction from GeomBase to Strips Cover Box (hist | edit) ‎[444 bytes] ‎Admin (talk | contribs) (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")
• 11:18, 15 February 2023 ‎Reduction from GeomBase to Separator2 (hist | edit) ‎[438 bytes] ‎Admin (talk | contribs) (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")
• 11:18, 15 February 2023 ‎Reduction from GeomBase to Separator1 (hist | edit) ‎[438 bytes] ‎Admin (talk | contribs) (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")
• 11:18, 15 February 2023 ‎Reduction from 3SUM to 3 Points on Line (hist | edit) ‎[440 bytes] ‎Admin (talk | contribs) (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")
• 11:18, 15 February 2023 ‎Reduction from 3 Points on Line to Point on 3 Lines (hist | edit) ‎[452 bytes] ‎Admin (talk | contribs) (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")
• 11:18, 15 February 2023 ‎Reduction from 3SUM' to GeomBase (hist | edit) ‎[433 bytes] ‎Admin (talk | contribs) (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")
• 11:18, 15 February 2023 ‎Reduction from GeomBase to 3SUM' (hist | edit) ‎[433 bytes] ‎Admin (talk | contribs) (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")
• 11:18, 15 February 2023 ‎Reduction from 3SUM' to 3SUM (hist | edit) ‎[429 bytes] ‎Admin (talk | contribs) (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")
• 11:18, 15 February 2023 ‎Reduction from Partial Match to OV (hist | edit) ‎[332 bytes] ‎Admin (talk | contribs) (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")
• 11:18, 15 February 2023 ‎Reduction from CNF-SAT to Frechet Distance (hist | edit) ‎[495 bytes] ‎Admin (talk | contribs) (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...")
• 11:18, 15 February 2023 ‎Reduction from OV to Partial Match (hist | edit) ‎[332 bytes] ‎Admin (talk | contribs) (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")
• 11:18, 15 February 2023 ‎Reduction from 3SUM to 3SUM' (hist | edit) ‎[429 bytes] ‎Admin (talk | contribs) (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")
• 11:18, 15 February 2023 ‎Reduction from UOV to Longest Common Subsequence (hist | edit) ‎[300 bytes] ‎Admin (talk | contribs) (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")
• 11:18, 15 February 2023 ‎Reduction from UOV to Dynamic Time Warping (hist | edit) ‎[294 bytes] ‎Admin (talk | contribs) (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")
• 11:18, 15 February 2023 ‎Reduction from OV to Edit Distance (hist | edit) ‎[536 bytes] ‎Admin (talk | contribs) (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:18, 15 February 2023 ‎Reduction from OV to Diameter 2 vs 3 (hist | edit) ‎[506 bytes] ‎Admin (talk | contribs) (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...")
• 11:18, 15 February 2023 ‎Reduction from 3-OV to Diameter 3 vs 7 (hist | edit) ‎[469 bytes] ‎Admin (talk | contribs) (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")

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