New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 100 | older 100) (20 | 50 | 100 | 250 | 500)
- 08:55, 10 April 2023 David (Square Matrix LU Decomposition LU Decomposition) (hist | edit) [238 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n \log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference ==")
- 08:55, 10 April 2023 Closed formula (Square Matrix LU Decomposition LU Decomposition) (hist | edit) [238 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n \log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference ==")
- 08:54, 10 April 2023 Hirschberg's algorithm (Edit sequence Sequence Alignment) (hist | edit) [329 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(n)$ words (https://dl.acm.org/doi/10.1145/360825.360861) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://dl.acm.org/doi/10.1145/360825.360861")
- 08:54, 10 April 2023 Masek; Patterson (Edit distance Sequence Alignment) (hist | edit) [382 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn / log(n))$ == Space Complexity == $O(n)$ words (https://www.sciencedirect.com/science/article/pii/0022000080900021) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://www.sciencedirect.com/science/article/pii/0022000080900021")
- 08:53, 10 April 2023 No-Steal, Force (hist | edit) [492 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:No-Steal, Force (Recovery)}} == Description == Recovery is the process of reverting back to a safe state prior to a system failure. With a No-Steal/Force policy, the recovery algorithm will never write uncommited data to memory, but will force all commits to memory. == Related Problems == Related: Steal, No-Force == Parameters == $n$: number of transactions before crash == Table of Algorithms == Currently no algorithms in our database for t...")
- 08:53, 10 April 2023 Steal, No-Force (hist | edit) [914 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Steal, No-Force (Recovery)}} == Description == Recovery is the process of reverting back to a safe state prior to a system failure. With a Steal/No-Force policy, the recovery algorithm will write possibly uncommited data to memory, while not forcing all commits to memory. == Related Problems == Related: No-Steal, Force == Parameters == $n$: number of transactions before crash == Table of Algorithms == {| class="wikitable sortable" style="t...")
- 08:53, 10 April 2023 Unweighted Interval Scheduling, Online (hist | edit) [3,094 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Unweighted Interval Scheduling, Online (Interval Scheduling)}} == Description == Given are $n$ intervals of the form $(s_j , f_j)$ with $s_j < f_j$, for $j = 1, \ldots , n$. These intervals are the jobs that require uninterrupted processing during that interval. We will assume (without loss of generality) that the $s_j$’s and the $f_j$’s are nonnegative integers. We say that two intervals (or jobs) overlap if their intersection is nonempty, otherwise...")
- 08:52, 10 April 2023 Root Computation with continuous first derivative (hist | edit) [764 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Root Computation with continuous first derivative (Root Computation)}} == Description == Given a real function with continuous first derivative, compute one of the roots. == Related Problems == Related: General Root Computation == Parameters == $\epsilon$: (additive) tolerance error $a, b$: endpoint values, with $b>a$ $n_{max}$: maximum number of iterations == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;"...")
- 08:52, 10 April 2023 General Root Computation (hist | edit) [2,713 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:General Root Computation (Root Computation)}} == Description == Given a real continuous function, compute one of the roots. == Related Problems == Related: Root Computation with continuous first derivative == Parameters == $\epsilon$: (additive) tolerance error $a, b$: endpoint values, with $b>a$ $n_{max}$: maximum number of iterations == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name...")
- 15:52, 15 February 2023 Reduction from OV to Disjunctive Reachability Queries in MDPs (hist | edit) [563 bytes] Admin (talk | contribs) (Created page with "FROM: OV TO: Disjunctive Reachability Queries in MDPs == Description == == Implications == assume: Strong Triangle<br/>then: there is no $O(m^{2-\epsilon})$ or $O((k \cdot m)^{1-\epsilon})$ algorithm, for any $\epsilon > {0}$ for target. == Year == 2016 == Reference == Chatterjee, Krishnendu, et al. "Model and objective separation with conditional lower bounds: Disjunction is harder than conjunction." Proceedings of the 31st Annual ACM/IEEE Symposium...")
- 12:19, 15 February 2023 Reduction from OV to k-OV (hist | edit) [135 bytes] Admin (talk | contribs) (Created page with "FROM: OV TO: k-OV == Description == == Implications == == Year == == Reference ==")
- 12:19, 15 February 2023 Reduction from 3-OV to k-OV (hist | edit) [141 bytes] Admin (talk | contribs) (Created page with "FROM: 3-OV TO: k-OV == Description == == Implications == == Year == == Reference ==")
- 12:19, 15 February 2023 Reduction from Max-Weight K-Clique to Weighted Depth (hist | edit) [619 bytes] Admin (talk | contribs) (Created page with "FROM: Max-Weight K-Clique TO: Weighted Depth == Description == == Implications == if: to-time: $O(n^{\lfloor d/{2}\rfloor-\epsilon})$ for $N$ weighted axis-parallel boxes in $\mathbb{R}^d$<br/>then: from-time: $O(n^{k-{2}\epsilon})$ on $n$ vertex graphs for $k=d$ == Year == 2016 == Reference == Backurs, Arturs, Nishanth Dikkala, and Christos Tzamos. "Tight Hardness Results for Maximum Weight Rectangles}}." 43rd International Colloquium on Automata,...")
- 12:19, 15 February 2023 Reduction from Max-Weight k-Clique to Maximum Subarray (hist | edit) [623 bytes] Admin (talk | contribs) (Created page with "FROM: Max-Weight k-Clique TO: Maximum Subarray == Description == == Implications == if: to-time: $O(n^{d+\lfloor d/{2}\rfloor-\epsilon})$ for $d$-dimensional hypercube arrays<br/>then: from-time: $O(n^{k-\epsilon})$ on $n$ vertex graphs for $k=d+\lfloor d/{2}\rfloor$ == Year == 2016 == Reference == Backurs, Arturs, Nishanth Dikkala, and Christos Tzamos. "Tight Hardness Results for Maximum Weight Rectangles}}." 43rd International Colloquium on Automa...")
- 12:19, 15 February 2023 Reduction from Max-Weight K-Clique to Maximum Square Subarray (hist | edit) [596 bytes] Admin (talk | contribs) (Created page with "FROM: Max-Weight K-Clique TO: Maximum Square Subarray == Description == == Implications == if: to-time: $O(n^{d+{1}-\epsilon})$ for $d$-dimensional hypercube arrays<br/>then: from-time: $O(n^{k-\epsilon})$ on $n$ vertex graphs for $k=d+{1}$ == Year == 2016 == Reference == Backurs, Arturs, Nishanth Dikkala, and Christos Tzamos. "Tight Hardness Results for Maximum Weight Rectangles}}." 43rd International Colloquium on Automata, Languages, and Programm...")
- 12:19, 15 February 2023 Reduction from Weighted, Undirected APSP to 2D Maximum Subarray (hist | edit) [572 bytes] Admin (talk | contribs) (Created page with "FROM: Weighted, Undirected APSP TO: 2D Maximum Subarray == Description == == Implications == if: to-time: $O(n^{3-\epsilon})$ on $n\times n$ matrices<br/>then: from-time: $O(n^{3-\epsilon/{1}0})$ on $n$ vertex graphs == Year == 2016 == Reference == Backurs, Arturs, Nishanth Dikkala, and Christos Tzamos. "Tight Hardness Results for Maximum Weight Rectangles}}." 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Vol. 5...")
- 12:19, 15 February 2023 Reduction from Negative Triangle Detection to 2D Maximum Subarray (hist | edit) [569 bytes] Admin (talk | contribs) (Created page with "FROM: Negative Triangle Detection TO: 2D Maximum Subarray == Description == == Implications == if: to-time: $O(n^{3-\epsilon})$ on $n\times n$ matrices<br/>then: from-time: $O(n^{3-\epsilon})$ on $n$ vertex graphs == Year == 2016 == Reference == Backurs, Arturs, Nishanth Dikkala, and Christos Tzamos. "Tight Hardness Results for Maximum Weight Rectangles}}." 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Vol. 55....")
- 12:19, 15 February 2023 Reduction from Max-Weight k-Clique to Max-Weight Rectangle (hist | edit) [616 bytes] Admin (talk | contribs) (Created page with "FROM: Max-Weight k-Clique TO: Max-Weight Rectangle == Description == == Implications == if: to-time: $O(N^{d-\epsilon})$ on $N$ weighted points in $d$ dimensions<br/>then: from-time: $O(n^{k-\epsilon})$ on $n$ vertices, where $k=\lceil d^{2}\epsilon^{-1}\rceil$ == Year == 2016 == Reference == Backurs, Arturs, Nishanth Dikkala, and Christos Tzamos. "Tight Hardness Results for Maximum Weight Rectangles}}." 43rd International Colloquium on Automata, Lan...")
- 12:19, 15 February 2023 Reduction from Bichromatic Hamming Close Pair to Approximate Hard-Margin SVM (hist | edit) [701 bytes] Admin (talk | contribs) (Created page with "FROM: Bichromatic Hamming Close Pair TO: Approximate Hard-Margin SVM == Description == == Implications == assume: SETH<br/>then: let $k(a,a')$ be the Gaussian kernel with $C={100}\log n$ and let $\epsilon = \exp(-\omega(\log^{2} n))$, then approximating the optimal value of target within multiplicative factor ${1}+\epsilon$ requires almost quadratic time. == Year == 2017 == Reference == Backurs, A., Indyk, P., & Schmidt, L. (2017). On the fine-graine...")
- 12:19, 15 February 2023 Reduction from Maximum Inner Product Search to Stable Pair Checking (hist | edit) [641 bytes] Admin (talk | contribs) (Created page with "FROM: Maximum Inner Product Search TO: Stable Pair Checking == Description == == Implications == assume: OVH<br/>then: for any $\epsilon > {0}$, there is a $c$ such that determining whether a given pair is part of any or all stable matchings in the boolean $d$-attribute model with $d = c\log n$ dimensions requires time $\Omega(n^{2-\epsilon})$ == Year == 2016 == Reference == Moeller, Daniel, Ramamohan Paturi, and Stefan Schneider. "Subquadratic algor...")
- 12:19, 15 February 2023 Reduction from Maximum Inner Product Search to Stable Matching Verification (hist | edit) [585 bytes] Admin (talk | contribs) (Created page with "FROM: Maximum Inner Product Search TO: Stable Matching Verification == Description == == Implications == assume: OVH<br/>then: for an $\epsilon > {0}$ there is a $c$ such that verifying a stable matching in the boolean $d$-attribute model with $d = c\log n$ dimensions requires time $\Omega(n^{2-\epsilon}). == Year == 2016 == Reference == Moeller, Daniel, Ramamohan Paturi, and Stefan Schneider. "Subquadratic algorithms for succinct stable matching." I...")
- 12:19, 15 February 2023 Reduction from Maximum Inner Product Search to Boolean d-Attribute Stable Matching (hist | edit) [591 bytes] Admin (talk | contribs) (Created page with "FROM: Maximum Inner Product Search TO: Boolean d-Attribute Stable Matching == Description == == Implications == assume: OVH<br/>then: for an $\epsilon > {0}$ there is a $c$ such that finding a stable matching in the boolean $d$-attribute model with $d = c\log n$ dimensions requires time $\Omega(n^{2-\epsilon})$. == Year == 2016 == Reference == Moeller, Daniel, Ramamohan Paturi, and Stefan Schneider. "Subquadratic algorithms for succinct stable matchi...")
- 12:19, 15 February 2023 Reduction from OV to Disjunctive Queries of Safety in Graphs (hist | edit) [590 bytes] Admin (talk | contribs) (Created page with "FROM: OV TO: Disjunctive Queries of Safety in Graphs == Description == == Implications == assume: OVH<br/>then: there is no $O(m^{2-\epsilon})$ or $O((k \cdot m)^{1 - \epsilon})$ algorithm for any $\epsilon > {0}$ for disjunctive safety ovjectives/queries in MDPs. == Year == 2016 == Reference == Chatterjee, Krishnendu, et al. "Model and objective separation with conditional lower bounds: Disjunction is harder than conjunction." Proceedings of the 31s...")
- 12:19, 15 February 2023 Reduction from OV to Disjunctive Queries of Reachability in MDPs (hist | edit) [563 bytes] Admin (talk | contribs) (Created page with "FROM: OV TO: Disjunctive Queries of Reachability in MDPs == Description == == Implications == assume: Strong Triangle<br/>then: there is no $O(m^{2-\epsilon})$ or $O((k \cdot m)^{1-\epsilon})$ algorithm, for any $\epsilon > {0}$ for target. == Year == 2016 == Reference == Chatterjee, Krishnendu, et al. "Model and objective separation with conditional lower bounds: Disjunction is harder than conjunction." Proceedings of the 31st Annual ACM/IEEE Sympos...")
- 12:19, 15 February 2023 Reduction from Triangle Detection to Disjunctive Queries of Safety in Graphs (hist | edit) [642 bytes] Admin (talk | contribs) (Created page with "FROM: Triangle Detection TO: Disjunctive Queries of Safety in Graphs == Description == == Implications == assume: Strong Triangle<br/>then: there is no combinatorial $O(n^{3-\epsilon})$ or $O((k \cdot n^{2})^{1-\epsilon})$ algorithm, for any $\epsilon > {0}$ for disjunctive safety (objectives or queries) in graphs. == Year == 2016 == Reference == Chatterjee, Krishnendu, et al. "Model and objective separation with conditional lower bounds: Disjunction...")
- 12:19, 15 February 2023 Reduction from Triangle Detection to Disjunctive Queries of Reachability in MDPs (hist | edit) [653 bytes] Admin (talk | contribs) (Created page with "FROM: Triangle Detection TO: Disjunctive Queries of Reachability in MDPs == Description == == Implications == assume: Strong Triangle<br/>then: there is no combinatorial $O(n^{3-\epsilon})$ or $O((k \cdot n^{2})^{1-\epsilon})$ algorithm for any $\epsilon > {0}$ for target. The bounds holf for dense MDPs with $m=\Theta(n^{2})$ == Year == 2016 == Reference == Chatterjee, Krishnendu, et al. "Model and objective separation with conditional lower bounds:...")
- 12: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...")
- 12: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...")
- 12: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...")
- 12: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...")
- 12: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...")
- 12: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...")
- 12: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...")
- 12: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...")
- 12: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...")
- 12: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.,...")
- 12: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....")
- 12: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...")
- 12: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...")
- 12: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...")
- 12: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...")
- 12: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...")
- 12: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...")
- 12: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...")
- 12: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...")
- 12: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...")
- 12: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...")
- 12: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:...")
- 12: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:...")
- 12: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...")
- 12: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...")
- 12: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...")
- 12: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...")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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...")
- 12: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")
- 12: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")
- 12: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")
- 12: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")
- 12: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...")
- 12: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...")
- 12: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")
- 12:18, 15 February 2023 Reduction from CNF-SAT to k-OV (hist | edit) [466 bytes] Admin (talk | contribs) (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.")
- 12:18, 15 February 2023 Fagin (4NF Decomposition for Functional and Multivalued Dependency Sets 4NF Decomposition) (hist | edit) [350 bytes] Admin (talk | contribs) (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")
- 12:18, 15 February 2023 Sciore (4NF Decomposition for Conflict-Free Dependency Sets 4NF Decomposition) (hist | edit) [285 bytes] Admin (talk | contribs) (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")
- 12:18, 15 February 2023 Lien (4NF Decomposition for Conflict-Free Dependency Sets 4NF Decomposition) (hist | edit) [387 bytes] Admin (talk | contribs) (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")
- 12:18, 15 February 2023 Grahne and Räihä (4NF Decomposition for Functional and Multivalued Dependency Sets 4NF Decomposition) (hist | edit) [360 bytes] Admin (talk | contribs) (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")
- 12:18, 15 February 2023 Global Newton Method (n player games Nash Equilibria) (hist | edit) [307 bytes] Admin (talk | contribs) (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")
- 12:18, 15 February 2023 Mixed Integer Programming (n player games Nash Equilibria) (hist | edit) [292 bytes] Admin (talk | contribs) (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")
- 12:18, 15 February 2023 Support enumeration and search (n player games Nash Equilibria) (hist | edit) [293 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == Unknown == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 2004 == Reference == https://www.aaai.org/Library/AAAI/2004/aaai04-105.php")
- 12:18, 15 February 2023 Lipton, Markakis and Mehta method 2 (n player games Nash Equilibria) (hist | edit) [357 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{ck^{2} log (k^{2}n)$/eps^2}) == Space Complexity == $O(k^{2}log^{2} n/eps^{2})$ words () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM words == Year == 2003 == Reference == https://dl.acm.org/doi/10.1145/779928.779933")
- 12:18, 15 February 2023 Lipton, Markakis and Mehta method (2 player games Nash Equilibria) (hist | edit) [340 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{c log n/eps^2})$ == Space Complexity == $O(log^{2} n/eps^{2})$ words () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM words == Year == 2003 == Reference == https://dl.acm.org/doi/10.1145/779928.779933")
- 12:18, 15 February 2023 Treap ( Self-Balancing Trees Search) (hist | edit) [292 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1989 == Reference == http://faculty.washington.edu/aragon/pubs/rst89.pdf")
- 12:18, 15 February 2023 Blum, Shelton, Koller (Graphical games, Multi-agent influence diagrams Nash Equilibria) (hist | edit) [396 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == Unknown? == Space Complexity == words () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2003 == Reference == https://www.semanticscholar.org/paper/A-Continuation-Method-for-Nash-Equilibria-in-Games-Blum-Shelton/4a3b80041922298db147debc2a2307bc4a5a42e9")
- 12:18, 15 February 2023 Tango Tree ( Self-Balancing Trees Search) (hist | edit) [303 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((k+{1})$log(log(n))) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == http://erikdemaine.org/papers/Tango_SICOMP/paper.pdf")
- 12:18, 15 February 2023 Lemke-Howson Algorithm (2 player games Nash Equilibria) (hist | edit) [335 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == Exponential == Space Complexity == $O(mn)$? words (I am not sure if this can be optimized?) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1964 == Reference == https://doi.org/10.1137/0112033")
- 12:18, 15 February 2023 Scapegoat Tree ( Self-Balancing Trees Search) (hist | edit) [322 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.4859")
- 12:18, 15 February 2023 Bayer, McCreight B-Tree ( Self-Balancing Trees Search) (hist | edit) [264 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b*log(n)$/log(b))? == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==")
- 12:18, 15 February 2023 Tarjan Splay Tree ( Self-Balancing Trees Search) (hist | edit) [249 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference ==")
- 12:18, 15 February 2023 Treap ( Self-Balancing Trees Deletion) (hist | edit) [292 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1989 == Reference == http://faculty.washington.edu/aragon/pubs/rst89.pdf")
- 12:18, 15 February 2023 AVL Tree ( Self-Balancing Trees Search) (hist | edit) [353 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (Need to keep track of constant amount of info during search (i.e. which node we're on and what direction to go)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference ==")
- 12:18, 15 February 2023 Scapegoat Tree ( Self-Balancing Trees Deletion) (hist | edit) [318 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.4859")
- 12:18, 15 February 2023 Bayer, McCreight B-Tree ( Self-Balancing Trees Deletion) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b*log(n)$/log(b))? == Space Complexity == $O(b)$? words (^see above, but with branching factor involved) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==")
- 12:18, 15 February 2023 AVL Tree ( Self-Balancing Trees Deletion) (hist | edit) [252 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference ==")
- 12:18, 15 February 2023 Treap ( Self-Balancing Trees Insertion) (hist | edit) [292 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1989 == Reference == http://faculty.washington.edu/aragon/pubs/rst89.pdf")
- 12:18, 15 February 2023 Scapegoat Tree ( Self-Balancing Trees Insertion) (hist | edit) [318 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.4859")