All public logs
Jump to navigation
Jump to search
Combined display of all available logs of Algorithm Wiki. You can narrow down the view by selecting a log type, the username (case-sensitive), or the affected page (also case-sensitive).
(newest | oldest) View (newer 500 | older 500) (20 | 50 | 100 | 250 | 500)- 12:27, 15 February 2023 Admin talk contribs uploaded File:Nearest Neighbor Search - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Kth Order Statistic - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Kth Order Statistic - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Clique Problems - Enumerating Maximal Cliques, arbitrary graph - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Clique Problems - Enumerating Maximal Cliques, arbitrary graph - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:CFG Problems - CFG Parsing - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:CFG Problems - CFG Parsing - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Linear System - Vandermonde Matrix - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Shortest Path (Directed Graphs) - Nonnegative Weights - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Linear System - Vandermonde Matrix - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Shortest Path (Directed Graphs) - Nonnegative Weights - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Graph Coloring - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Graph Coloring - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:All-Pairs Shortest Paths (APSP) - APSP - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:All-Pairs Shortest Paths (APSP) - APSP - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Clique Problems - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:LU Decomposition - Square Matrix LU Decomposition - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Clique Problems - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:LU Decomposition - Square Matrix LU Decomposition - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Polygon Clipping - Polygon Clipping with Arbitrary Clipping Polygon - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Polygon Clipping - Polygon Clipping with Arbitrary Clipping Polygon - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Cyclic Peptide Sequencing Problem - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Cyclic Peptide Sequencing Problem - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Logarithm Calculations - Discrete Logarithm Over Finite Fields - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Logarithm Calculations - Discrete Logarithm Over Finite Fields - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:All-Pairs Shortest Paths (APSP) - APSP on Dense Undirected Unweighted Graphs - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:All-Pairs Shortest Paths (APSP) - APSP on Dense Undirected Unweighted Graphs - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Graph Edit Distance Computation - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Register Allocation - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Graph Edit Distance Computation - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Register Allocation - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Stable Matching Problem - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Duplicate Elimination - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Duplicate Elimination - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Stable Matching Problem - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Sequence Alignment - Edit Sequence, constant-size alphabet - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Sequence Alignment - Edit Sequence, constant-size alphabet - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:String Search - Single String Search - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Line Clipping - Convex Polygonal Window - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:String Search - Single String Search - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Line Clipping - Convex Polygonal Window - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:AST to Code Translation - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:AST to Code Translation - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Link Analysis - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:String Search - Single String Search - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Link Analysis - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Dependency Inference Problem - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:String Search - Single String Search - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Dependency Inference Problem - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Cardinality Estimation - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Cardinality Estimation - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Cycle Detection - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Cycle Detection - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Recovery - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Recovery - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Linear System - General Linear System - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Eigenvalues (Iterative Methods) - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Matrix Product - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Eigenvalues (Iterative Methods) - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Matrix Product - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Linear System - General Linear System - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Stable Matching Problem - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:AST to Code Translation - Arithmetic Expression Binary Tree - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Stable Matching Problem - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:AST to Code Translation - Arithmetic Expression Binary Tree - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:BCNF Decomposition - Decisional BCNF - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:BCNF Decomposition - Decisional BCNF - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Graph Coloring - 4-Graph Coloring - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Graph Coloring - 4-Graph Coloring - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Cardinality Estimation - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:All-Pairs Shortest Paths (APSP) - APSP on Sparse Undirected Graphs with Positive Integer Weights - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Transitive Reduction Problem - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:All-Pairs Shortest Paths (APSP) - APSP on Sparse Undirected Graphs with Positive Integer Weights - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Cardinality Estimation - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Transitive Reduction Problem - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Delaunay Triangulation - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Delaunay Triangulation - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Maximum-Weight Matching - Bipartite Maximum-Weight Matching - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Maximum-Weight Matching - Bipartite Maximum-Weight Matching - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:N-Queens Problem - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:N-Queens Problem - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Joins - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:AST to Code Translation - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Sorting - Non-Comparison Sorting - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Joins - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Maximum Flow - st-Maximum Flow - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Sorting - Non-Comparison Sorting - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:AST to Code Translation - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Maximum Flow - st-Maximum Flow - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Cryptanalysis of Linear Feedback Shift Registers - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Cryptanalysis of Linear Feedback Shift Registers - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:The Subset-Sum Problem - Subset Sum - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:The Subset-Sum Problem - Subset Sum - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Strongly Connected Components - Transitive Closure - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Strongly Connected Components - Transitive Closure - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Link Analysis - InDegree Analysis - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Link Analysis - InDegree Analysis - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:De Novo Genome Assembly - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Link Analysis - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:De Novo Genome Assembly - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Link Analysis - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Dependency Inference Problem - Functional Dependency Inference Problem - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Dependency Inference Problem - Functional Dependency Inference Problem - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Sorting - Non-Comparison Sorting - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Sorting - Non-Comparison Sorting - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Solutions to Nonlinear Equations - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Solutions to Nonlinear Equations - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Stable Matching Problem - Stable Roommates Problem - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Linear System - Non-Definite, Symmetric Matrix - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Stable Matching Problem - Stable Roommates Problem - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Linear System - Non-Definite, Symmetric Matrix - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Greatest Common Divisor - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Greatest Common Divisor - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:The Frequent Words Problem - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:The Frequent Words Problem - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Stable Matching Problem - Stable Roommates Problem - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Recovery - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Stable Matching Problem - Stable Roommates Problem - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Recovery - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Nearest Neighbor Search - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Nearest Neighbor Search - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Motif Search - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:SDD Systems Solvers - Exact Laplacian Solver - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Motif Search - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:SDD Systems Solvers - Exact Laplacian Solver - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Matrix Chain Multiplication - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Matrix Chain Multiplication - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Optimal Policies for MDPs - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:4NF Decomposition - 4NF Decomposition for Conflict-Free Dependency Sets - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Optimal Policies for MDPs - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:4NF Decomposition - 4NF Decomposition for Conflict-Free Dependency Sets - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:The Set-Covering Problem - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:The Set-Covering Problem - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:BCNF Decomposition - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:BCNF Decomposition - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Graph Edit Distance Computation - Exact GED - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Graph Edit Distance Computation - Exact GED - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Self-Balancing Trees Insertion - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Page Replacements - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Page Replacements - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Self-Balancing Trees Insertion - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Polygon Clipping - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Tower of Hanoi - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Polygon Clipping - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Tower of Hanoi - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Distributed Locking Algorithms - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Distributed Locking Algorithms - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:All-Pairs Shortest Paths (APSP) - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Linear System - Positive Definite, Hermitian Matrix - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:All-Pairs Shortest Paths (APSP) - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Linear System - Positive Definite, Hermitian Matrix - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Polynomial Interpolation - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Disk Scheduling - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Disk Scheduling - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Polynomial Interpolation - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Longest Path Problem - Longest Path on Interval Graphs - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Longest Path Problem - Longest Path on Interval Graphs - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Factorization of Polynomials Over Finite Fields - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Interval Scheduling - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Interval Scheduling - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Factorization of Polynomials Over Finite Fields - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Point-in-Polygon - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Collaborative Filtering - Matrix Factorization - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Point-in-Polygon - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Collaborative Filtering - Matrix Factorization - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Median String Problem - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Median String Problem - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:All-Pairs Shortest Paths (APSP) - APSP on Sparse Undirected Unweighted Graphs - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Integer Factoring - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:All-Pairs Shortest Paths (APSP) - APSP on Sparse Undirected Unweighted Graphs - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Integer Factoring - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Stable Matching Problem - Stable Marriage Problem - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Convex Optimization (Non-linear) - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Stable Matching Problem - Stable Marriage Problem - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Convex Optimization (Non-linear) - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Shortest Path (Directed Graphs) - Nonnegative Weights - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Shortest Path (Directed Graphs) - Nonnegative Weights - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Kth Order Statistic - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Kth Order Statistic - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Graph Coloring - 4-Graph Coloring - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Graph Coloring - 4-Graph Coloring - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Shortest Path (Directed Graphs) - Nonnegative Weights - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Shortest Path (Directed Graphs) - Nonnegative Weights - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Line segment intersection - Reporting all intersection points, line segments - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Matrix Chain Multiplication - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Line segment intersection - Reporting all intersection points, line segments - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Matrix Chain Multiplication - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Lowest Common Ancestor - Off-Line Lowest Common Ancestor - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Lowest Common Ancestor - Off-Line Lowest Common Ancestor - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Graph Coloring - 3-Graph Coloring - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Graph Coloring - 3-Graph Coloring - Time.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Link Analysis - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Link Analysis - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Page Replacements - Online - Space.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Page Replacements - Online - Space.png
- 12:27, 15 February 2023 Admin talk contribs created page File:Dependency Inference Problem - Multivalued Dependency Inference Problem - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:Dependency Inference Problem - Multivalued Dependency Inference Problem - Pareto Frontier.png
- 12:27, 15 February 2023 Admin talk contribs created page File:All Permutations - Time.png
- 12:27, 15 February 2023 Admin talk contribs uploaded File:All Permutations - Time.png
- 12:19, 15 February 2023 Admin talk contribs created page Reduction from OV to k-OV (Created page with "FROM: OV TO: k-OV == Description == == Implications == == Year == == Reference ==")
- 12:19, 15 February 2023 Admin talk contribs created page Reduction from 3-OV to k-OV (Created page with "FROM: 3-OV TO: k-OV == Description == == Implications == == Year == == Reference ==")
- 12:19, 15 February 2023 Admin talk contribs created page Reduction from Max-Weight K-Clique to Weighted Depth (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 Admin talk contribs created page Reduction from Max-Weight K-Clique to Maximum Square Subarray (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 Admin talk contribs created page Reduction from Max-Weight k-Clique to Maximum Subarray (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 Admin talk contribs created page Reduction from Weighted, Undirected APSP to 2D Maximum Subarray (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 Admin talk contribs created page Reduction from Negative Triangle Detection to 2D Maximum Subarray (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 Admin talk contribs created page Reduction from Max-Weight k-Clique to Max-Weight Rectangle (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 Admin talk contribs created page Reduction from Bichromatic Hamming Close Pair to Approximate Hard-Margin SVM (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 Admin talk contribs created page Reduction from Maximum Inner Product Search to Stable Pair Checking (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 Admin talk contribs created page Reduction from Maximum Inner Product Search to Stable Matching Verification (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 Admin talk contribs created page Reduction from Maximum Inner Product Search to Boolean d-Attribute Stable Matching (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 Admin talk contribs created page Reduction from OV to Disjunctive Queries of Safety in Graphs (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 Admin talk contribs created page Reduction from OV to Disjunctive Queries of Reachability in MDPs (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 Admin talk contribs created page Reduction from Triangle Detection to Disjunctive Queries of Safety in Graphs (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 Admin talk contribs created page Reduction from Triangle Detection to Disjunctive Queries of Reachability in MDPs (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 Admin talk contribs created page Reduction from OV to Generalized Büchi Games (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 Admin talk contribs created page Reduction from Triangle Detection to Disjunctive coBüchi Objectives (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 Admin talk contribs created page Reduction from OV to Largest Common Subtree (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 Admin talk contribs created page Reduction from k-SAT to Subset Sum (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 Admin talk contribs created page Reduction from OV to Subtree Isomorphism (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 Admin talk contribs created page Reduction from k-Clique to RNA Folding (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 Admin talk contribs created page Reduction from k-Clique to CFG Recognition (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 Admin talk contribs created page Reduction from OV to Bichromatic Hamming Close Pair (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 Admin talk contribs created page Reduction from CNF-SAT to sensitive incremental ST-Reach (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 Admin talk contribs created page Reduction from CNF-SAT to constant sensitivity (4/3)-approximate incremental diameter (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 Admin talk contribs created page Reduction from Directed, Weighted APSP to 1-sensitive decremental diameter (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 Admin talk contribs created page Reduction from CNF-SAT to sensitive incremental (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 Admin talk contribs created page Reduction from Directed, Weighted APSP to 2-sensitive decremental st-shortest paths (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 Admin talk contribs created page Reduction from Replacement Paths Problem (RPP) to 1-sensitive decremental st-shortest paths (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 Admin talk contribs created page Reduction from BMM to 1-sensitive decremental st-shortest paths (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 Admin talk contribs created page Reduction from BMM to 1-sensitive (4/3)-approximate decremental diameter (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 Admin talk contribs created page Reduction from BMM to 1-sensitive (4/3)-approximate decremental eccentricity (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 Admin talk contribs created page Reduction from BMM to (5/3)-approximate ap-shortest paths (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 Admin talk contribs created page Reduction from BMM to 1-sensitive (3/2)-approximate ss-shortest paths (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 Admin talk contribs created page Reduction from BMM to 2-sensitive (7/5)-approximate st-shortest paths (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 Admin talk contribs created page 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...")
- 12:19, 15 February 2023 Admin talk contribs created page 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:...")
- 12:19, 15 February 2023 Admin talk contribs created page 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:...")
- 12:19, 15 February 2023 Admin talk contribs created page 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...")
- 12:19, 15 February 2023 Admin talk contribs created page 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...")
- 12:19, 15 February 2023 Admin talk contribs created page 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...")
- 12:19, 15 February 2023 Admin talk contribs created page 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...")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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...")
- 12:18, 15 February 2023 Admin talk contribs created page 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...")
- 12:18, 15 February 2023 Admin talk contribs created page 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...")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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.")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page 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")
- 12:18, 15 February 2023 Admin talk contribs created page Support enumeration and search (n player games Nash Equilibria) (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 Admin talk contribs created page Lipton, Markakis and Mehta method 2 (n player games Nash Equilibria) (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 Admin talk contribs created page Lipton, Markakis and Mehta method (2 player games Nash Equilibria) (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 Admin talk contribs created page Treap ( Self-Balancing Trees Search) (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 Admin talk contribs created page Blum, Shelton, Koller (Graphical games, Multi-agent influence diagrams Nash Equilibria) (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 Admin talk contribs created page Tango Tree ( Self-Balancing Trees Search) (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 Admin talk contribs created page Lemke-Howson Algorithm (2 player games Nash Equilibria) (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 Admin talk contribs created page Scapegoat Tree ( Self-Balancing Trees Search) (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 Admin talk contribs created page Bayer, McCreight B-Tree ( Self-Balancing Trees Search) (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 Admin talk contribs created page Tarjan Splay Tree ( Self-Balancing Trees Search) (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 Admin talk contribs created page Treap ( Self-Balancing Trees Deletion) (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 Admin talk contribs created page AVL Tree ( Self-Balancing Trees Search) (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 Admin talk contribs created page Scapegoat Tree ( Self-Balancing Trees Deletion) (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 Admin talk contribs created page Bayer, McCreight B-Tree ( Self-Balancing Trees Deletion) (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 Admin talk contribs created page Tarjan Splay Tree ( Self-Balancing Trees Deletion) (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 Admin talk contribs created page Treap ( Self-Balancing Trees Insertion) (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 Admin talk contribs created page AVL Tree ( Self-Balancing Trees Deletion) (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 Admin talk contribs created page Scapegoat Tree ( Self-Balancing Trees Insertion) (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 Admin talk contribs created page Bayer, McCreight B-Tree ( Self-Balancing Trees Insertion) (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 Admin talk contribs created page Tarjan Splay Tree ( Self-Balancing Trees Insertion) (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 Admin talk contribs created page AVL Tree ( Self-Balancing Trees Insertion) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (Each node being changed requires constant auxiliary space to make changes; can reuse space across nodes being changed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference ==")
- 12:18, 15 February 2023 Admin talk contribs created page Scapegoat Tree ( Self-Balancing Trees Creation) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == 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 Admin talk contribs created page Treap ( Self-Balancing Trees Creation) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == 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 Admin talk contribs created page Tango Tree ( Self-Balancing Trees Creation) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == 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 Admin talk contribs created page Babai 1980 (Graph Isomorphism, Bounded Vertex Valences Graph Isomorphism Problem) (Created page with "== Time Complexity == \exp(n^{\frac{1}{2} + $O({1})$}) == Space Complexity == $O(n^{2})$ words (https://epubs.siam.org/doi/epdf/10.1137/0209018) == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Word RAM == Year == 1980 == Reference == https://epubs.siam.org/doi/10.1137/0209018")
- 12:18, 15 February 2023 Admin talk contribs created page Babai 1980 (Graph Isomporhism, Trivalent Graphs Graph Isomorphism Problem) (Created page with "== Time Complexity == \exp(cn^{\frac{1}{2}} \log n) == Space Complexity == $O(n^{2})$ words (https://epubs.siam.org/doi/epdf/10.1137/0209018) == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Word RAM == Year == 1980 == Reference == https://epubs.siam.org/doi/10.1137/0209018")
- 12:18, 15 February 2023 Admin talk contribs created page Gronlund, Pettie (3-Clique Exact-Weight k-Clique Problem) (Created page with "== Time Complexity == $O(n^{3}*(log log n)$^{2}/(log n)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2014 == Reference == https://ieeexplore.ieee.org/abstract/document/6979047")
- 12:18, 15 February 2023 Admin talk contribs created page Brute force enumeration (k-Clique k-Clique Problem) (Created page with "== Time Complexity == $O(n^k)$ == Space Complexity == $O(k)$ auxiliary words (keeping track of which vertices we're looking at) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 12:18, 15 February 2023 Admin talk contribs created page APSP algorithm (3-Clique Min-Weight k-Clique Problem) (Created page with "== Time Complexity == $O(n^{3} / {2}^(log n)$^{0.5}) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 12:18, 15 February 2023 Admin talk contribs created page Nesetril, Poljak (k-Clique k-Clique Problem) (Created page with "== Time Complexity == $O(n^(k-({3}-\omega)*floor(k/{3}))$ where omega is the exponent on matrix multiplication == Space Complexity == $O(n^({2}k/{3})$) ish words (matrix sizes) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == https://dml.cz/bitstream/handle/10338.dmlcz/106381/CommentatMathUnivCarol_026-1985-2_22.pdf")
- 12:18, 15 February 2023 Admin talk contribs created page Reduction to Chan, Williams (k-OV Orthogonal Vectors) (Created page with "== Time Complexity == $O(n^{(k-{1}/O(d/log(n)))})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2016 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611974331.ch87")
- 12:18, 15 February 2023 Admin talk contribs created page Chan, Williams (OV Orthogonal Vectors) (Created page with "== Time Complexity == $O(n^{({2}-{1}/O(d/log(n)))})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2016 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611974331.ch87")
- 12:18, 15 February 2023 Admin talk contribs created page Abboud, Williams, Yu (OV Orthogonal Vectors) (Created page with "== Time Complexity == $O(n^{({2}-{1}/O(d/log(n)))})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2015 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611973730.17")
- 12:18, 15 February 2023 Admin talk contribs created page Reduction to Abboud, Williams, Yu (k-OV Orthogonal Vectors) (Created page with "== Time Complexity == $O(n^{(k-{1}/O(d/log(n)))})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2015 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611973730.17")
- 12:18, 15 February 2023 Admin talk contribs created page Exhaustive search (Minimum Wiener Connector problem Wiener Index) (Created page with "== Time Complexity == {2}^($O(n)$) == Space Complexity == $O(n)$ auxiliary words (Keeps track of current subset being checked, minimum subset, and O(1) Wiener indices) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference ==")
- 12:18, 15 February 2023 Admin talk contribs created page Exhaustive search (k-OV Orthogonal Vectors) (Created page with "== Time Complexity == $O(d*n^k)$ == Space Complexity == $O(k)$ auxiliary words (keeping track of which vectors we're looking at) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 12:18, 15 February 2023 Admin talk contribs created page Wen (2-dimensional Maximum subarray problem) (Created page with "== Time Complexity == $O(log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW PRAM == Year == 1995 == Reference == https://www.sciencedirect.com/science/article/abs/pii/016781919400063G")
- 12:18, 15 February 2023 Admin talk contribs created page KALYAN PERUMALLA and NARSINGH DEO (2-dimensional Maximum subarray problem) (Created page with "== Time Complexity == $O(log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1995 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.1291&rep=rep1&type=pdf")
- 12:18, 15 February 2023 Admin talk contribs created page Takaoka (2-dimensional Maximum subarray problem) (Created page with "== Time Complexity == $O(n^{3} * ((log log n)$/(log n))^({1}/{2})) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://www.sciencedirect.com/science/article/pii/S1571066104003135?via%3Dihub")
- 12:18, 15 February 2023 Admin talk contribs created page Tamaki, Tokuyama (approximate) (2-dimensional Maximum subarray problem) (Created page with "== Time Complexity == $O(n^(omega)$ * (-log(epsilon))/epsilon) == Space Complexity == words () == Description == == Approximate? == Approximate Approximation Factor: (1-epsilon) == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://dl.acm.org/doi/pdf/10.5555/314613.314823")
- 12:18, 15 February 2023 Admin talk contribs created page Tamaki, Tokuyama (exact) (2-dimensional Maximum subarray problem) (Created page with "== Time Complexity == $O(n^{3} * ((log log n)$/(log n))^({1}/{2})) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://dl.acm.org/doi/pdf/10.5555/314613.314823")
- 12:18, 15 February 2023 Admin talk contribs created page Smith (2-dimensional Maximum subarray problem) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(log n)$ auxiliary? words (divide-and-conquer) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://www.sciencedirect.com/science/article/pii/0167642387900347")
- 12:18, 15 February 2023 Admin talk contribs created page Bentley (2-dimensional Maximum subarray problem) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ auxiliary? words ((i think you need to pre-process to get cumulative sums in each row?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://dl.acm.org/doi/pdf/10.1145/1968.381154")
- 12:18, 15 February 2023 Admin talk contribs created page Brute force (2-dimensional Maximum subarray problem) (Created page with "== Time Complexity == $O(n^{6})$ == Space Complexity == $O({1})$ auxiliary words (keep track of which subarray is being computed, along with current maximum) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1977 == Reference == -")
- 12:18, 15 February 2023 Admin talk contribs created page Stege, Fellows + Interleaving method (Niedermeier, Rossmanith) (The Vertex Cover Problem The Vertex Cover Problem) (Created page with "== Time Complexity == $O(kn+({1.2906})$^k) == Space Complexity == $O(k^{3})$ auxiliary? (potentially $O(k^{2})$??) words ((see remark in algo id #576)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://mediatum.ub.tum.de/doc/1094228/file.pdf")
- 12:18, 15 February 2023 Admin talk contribs created page Stege, Fellows (The Vertex Cover Problem The Vertex Cover Problem) (Created page with "== Time Complexity == $O(kn+max(({1.25542})$^k k^{2}, ({1.2906})^k k) == Space Complexity == $O(k^{3})$ auxiliary? (potentially $O(k^{2})$??) words ((see remark in algo id #576)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://www.research-collection.ethz.ch/bitstream/handle/20.500.11850/69332/eth-4359-01.pdf")
- 12:18, 15 February 2023 Admin talk contribs created page Papadimitriou and M Yannakakis 1996 + Buss (The Vertex Cover Problem The Vertex Cover Problem) (Created page with "== Time Complexity == $O({3}^k k^{2}+kn)$ == Space Complexity == $O(k^{2})$ auxiliary? words (Auxiliary graph contains O(k^2) edges unless the instance is rejected; rest of steps take O(k) auxiliary space at most) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1996 == Reference == https://www.sciencedirect.com/science/article/pii/S0022000096900586")
- 12:18, 15 February 2023 Admin talk contribs created page Downey, Fellows (The Vertex Cover Problem The Vertex Cover Problem) (Created page with "== Time Complexity == $O(kn+{2}^k k^{2})$ == Space Complexity == $O(k^{2})$ auxiliary words (Auxiliary graph contains O(k^2) edges unless the instance is rejected; rest of steps take O(k) auxiliary space at most) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.2.7270&rep=rep1&type=pdf")
- 12:18, 15 February 2023 Admin talk contribs created page Chan (Real 3SUM 3SUM) (Created page with "== Time Complexity == $O(n^{2}*(log log n)$^{$O({1})$}/(log n)^{2}) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2018 == Reference == https://dl.acm.org/doi/abs/10.1145/3363541")
- 12:18, 15 February 2023 Admin talk contribs created page Exhaustive search (The Vertex Cover Problem The Vertex Cover Problem) (Created page with "== Time Complexity == $O(C(n, k)$) (i.e. (n, k) binomial coefficient) == Space Complexity == $O(k)$ auxiliary words (Just need to keep track of current subset being checked) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:18, 15 February 2023 Admin talk contribs created page Freund (Real 3SUM 3SUM) (Created page with "== Time Complexity == $O(n^{2}*(log log n)$/(log n)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2017 == Reference == https://link.springer.com/article/10.1007/s00453-015-0079-6")
- 12:18, 15 February 2023 Admin talk contribs created page Gronlund, Pettie (Real 3SUM 3SUM) (Created page with "== Time Complexity == $O(n^{2}/((log n)$/(log log n))^{2}/{3}) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2014 == Reference == https://ieeexplore.ieee.org/abstract/document/6979047")
- 12:18, 15 February 2023 Admin talk contribs created page Baran, Demaine, Patrascu (Integer 3SUM 3SUM) (Created page with "== Time Complexity == $O(n^{2}/max(w/(log w)$^{2}, (log n)^{2}/(log log n)^{2})) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Word RAM == Year == 2008 == Reference == https://link.springer.com/article/10.1007/s00453-007-9036-3")
- 12:18, 15 February 2023 Admin talk contribs created page Textbook Sort-and-Binary-Search (Integer 3SUM 3SUM) (Created page with "== Time Complexity == $O(n^{2} log n)$ == Space Complexity == $O(n)$ words (Storing sorted list) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 12:18, 15 February 2023 Admin talk contribs created page Kazuhisa Makino, Takeaki Uno; Section 6 (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (Created page with "== Time Complexity == $O(delta^{4})$ == Space Complexity == $O(n+m)$ auxiliary(?) words (https://link.springer.com/chapter/10.1007/978-3-540-27810-8_23) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://link.springer.com/chapter/10.1007/978-3-540-27810-8_23")
- 12:18, 15 February 2023 Admin talk contribs created page Textbook Sort-and-Two-Sided-Traversal (Integer 3SUM 3SUM) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Storing sorted list) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 12:18, 15 February 2023 Admin talk contribs created page Kmett (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (Created page with "== Time Complexity == $O(m*log(h)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference == https://www.schoolofhaskell.com/user/edwardk/online-lca")
- 12:18, 15 February 2023 Admin talk contribs created page Fischer, Heun (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (Created page with "== Time Complexity == $O(m+n)$ == Space Complexity == $O(n)$ words (https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.64.5439) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.64.5439")
- 12:18, 15 February 2023 Admin talk contribs created page Schieber; Vishkin (Parallel) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (Created page with "== Time Complexity == $O(m+log(n)$) == Space Complexity == $O(n)$ total (auxiliary?) words (https://www.proquest.com/docview/919780720?pq-origsite=gscholar&fromopenview=true) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW PRAM == Year == 1988 == Reference == https://epubs.siam.org/doi/abs/10.1137/0217079?journalCode=smjcat")
- 12:18, 15 February 2023 Admin talk contribs created page Harel, Tarjan (Static Trees) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (Created page with "== Time Complexity == $O(n+m)$ == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://www.semanticscholar.org/paper/Fast-Algorithms-for-Finding-Nearest-Common-Harel-Tarjan/8867d059dda279b1aed4a0301e4e46f9daf65174")
- 12:18, 15 February 2023 Admin talk contribs created page Harel, Tarjan (Linking Roots) (Lowest Common Ancestor with Linking Roots Lowest Common Ancestor) (Created page with "== Time Complexity == $O(n+ m*alpha(m + n, n)$) where alpha is the inverse Ackermann function == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://www.semanticscholar.org/paper/Fast-Algorithms-for-Finding-Nearest-Common-Harel-Tarjan/8867d059dda279b1aed4a0301e4e...")
- 12:18, 15 February 2023 Admin talk contribs created page Sleator and Tarjan (Linking) (Lowest Common Ancestor with Linking Lowest Common Ancestor) (Created page with "== Time Complexity == $O(n+m*log(n)$) == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1983 == Reference == https://www.sciencedirect.com/science/article/pii/0022000083900065")
- 12:18, 15 February 2023 Admin talk contribs created page Sleator and Tarjan (Linking and Cutting) (Lowest Common Ancestor with Linking and Cutting Lowest Common Ancestor) (Created page with "== Time Complexity == $O(n+m*log(n)$) == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1983 == Reference == https://www.sciencedirect.com/science/article/pii/0022000083900065")
- 12:18, 15 February 2023 Admin talk contribs created page Modified van Leeuwen (Linking Roots) (Lowest Common Ancestor with Linking Roots Lowest Common Ancestor) (Created page with "== Time Complexity == $O(n+m*log(log(n)$)) == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == (Unpublished report)")
- 12:18, 15 February 2023 Admin talk contribs created page Modified van Leeuwen (Static Trees) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (Created page with "== Time Complexity == $O(n+m*log(log(n)$)) == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == (Unpublished report)")
- 12:18, 15 February 2023 Admin talk contribs created page Aho, Hopcroft, and Ullman (Static Trees) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (Created page with "== Time Complexity == $O((m+n)$*log(log(n))) == Space Complexity == $O(n*log(log(n)$)) words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/pdf/10.1145/800125.804056")
- 12:18, 15 February 2023 Admin talk contribs created page Brent-Dekker Method (General Root Computation Root Computation) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store previous 3 estimates x_i, x_{i-1}, and x_{i-2} along with function values f_i, f_{i-1}, f_{i-2}; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1973 ==...")
- 12:18, 15 February 2023 Admin talk contribs created page Aho, Hopcroft, and Ullman (Offline) (Off-Line Lowest Common Ancestor Lowest Common Ancestor) (Created page with "== Time Complexity == $O(n+ m*alpha(m + n, n)$) where alpha is the inverse Ackermann function == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/pdf/10.1145/800125.804056")
- 12:18, 15 February 2023 Admin talk contribs created page Aho, Hopcroft, and Ullman (Linking) (Lowest Common Ancestor with Linking Lowest Common Ancestor) (Created page with "== Time Complexity == $O((m+n)$*log(n)) == Space Complexity == $O(n*log(n)$) words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/pdf/10.1145/800125.804056")
- 12:18, 15 February 2023 Admin talk contribs created page Inverse quadratic interpolation (General Root Computation Root Computation) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store previous 3 estimates x_i, x_{i-1}, and x_{i-2} along with function values f_i, f_{i-1}, f_{i-2}; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940(?)...")
- 12:18, 15 February 2023 Admin talk contribs created page Steffensen's method (General Root Computation Root Computation) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store previous estimate x_i; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940(?) == Reference ==")
- 12:18, 15 February 2023 Admin talk contribs created page Householder's Method (Root Computation with continuous derivatives (up to d) Root Computation) (Created page with "== Time Complexity == $O(d*n_max)$? == Space Complexity == $O(d)$ words (Store current estimate x_i and the derivatives f' through f^{(d)} (assuming these take O(1) space each); iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940(?...")
- 12:18, 15 February 2023 Admin talk contribs created page Illinois Algorithm (General Root Computation Root Computation) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1971 == Reference == https://link.springer.com/article/10.1007/BF01934364")
- 12:18, 15 February 2023 Admin talk contribs created page Anderson–Björck algorithm (General Root Computation Root Computation) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1973 == Reference == https://link.springer.com/article/10.1007/BF01951936")
- 12:18, 15 February 2023 Admin talk contribs created page ITP Method (General Root Computation Root Computation) (Created page with "== Time Complexity == $O(n_0+log((b-a)$/epsilon)) == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940? == Reference == -")
- 12:18, 15 February 2023 Admin talk contribs created page Gabow, Galil, Spencer (general Maximum-weight matching) (Created page with "== Time Complexity == $O(mn*log(log(log(n)$/log({2}+m/n))) + n^{2}*log(n)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://ieeexplore.ieee.org/abstract/document/715935")
- 12:18, 15 February 2023 Admin talk contribs created page Galil, Micali, Gabow (general Maximum-weight matching) (Created page with "== Time Complexity == $O(mn*log(n)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1982 == Reference == https://www.proquest.com/docview/919855909?pq-origsite=gscholar&fromopenview=true")
- 12:18, 15 February 2023 Admin talk contribs created page Gabow (general Maximum-weight matching) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://www.proquest.com/docview/287948024?pq-origsite=gscholar&fromopenview=true")
- 12:18, 15 February 2023 Admin talk contribs created page Johnson (Edmonds-Karp-based) (bipartite (i.e. assignment), general Maximum-weight matching) (Created page with "== Time Complexity == $O(mn*log(n)$/log({2}+m/n)) == Space Complexity == $O(n^{2})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://www.sciencedirect.com/science/article/pii/0020019075900010")
- 12:18, 15 February 2023 Admin talk contribs created page Edmonds-Karp (bipartite (i.e. assignment), general Maximum-weight matching) (Created page with "== Time Complexity == $O(n*(SP+))$ where $(SP+)$ denotes the time for one SSSP computation on a nonnegatively weighted graph. Initially $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Keeps track of current flow, which is of size O(n^2), and an O(n)-sized labeling function. SSSP computation has time bounded by O(n^2) and thus should use O(n^2) space at most) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Co...")
- 12:18, 15 February 2023 Admin talk contribs created page Fredman-Tarjan (Edmonds-Karp-based) (bipartite (i.e. assignment), general Maximum-weight matching) (Created page with "== Time Complexity == $O(mn+n^{2}log(n)$) == Space Complexity == $O(n^{2})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://dl.acm.org/doi/10.1145/28869.28874")
- 12:18, 15 February 2023 Admin talk contribs created page Zaks' prefix reversal algorithm ( All permutations) (Created page with "== Time Complexity == $O(n)$ on specific permutations == Space Complexity == $O(n)$ auxiliary (see NEXT algorithm in same paper) words (https://link.springer.com/content/pdf/10.1007/BF01937486.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://link.springer.com/article/10.1007/BF01937486")
- 12:18, 15 February 2023 Admin talk contribs created page Ives' algorithm c ( All permutations) (Created page with "== Time Complexity == $O({1})$ per permutation == Space Complexity == $O(n)$ auxiliary words (O(n) words needed to keep track of which elements have cycled how many times) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/abs/10.1145/359997.360002")
- 12:18, 15 February 2023 Admin talk contribs created page Ord-Smith ( All permutations) (Created page with "== Time Complexity == $O({1})$ per permutation == Space Complexity == $O(n)$ auxiliary words (O(n)-sized array q (as in paper) necessary) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1967 == Reference == https://dl.acm.org/doi/pdf/10.1145/362896.362913")
- 12:18, 15 February 2023 Admin talk contribs created page Langdon ( All permutations) (Created page with "== Time Complexity == $O(n)$ per permutation == Space Complexity == $O({1})$ auxiliary words (Only need the auxiliary variable N, according to the flowchart in the paper) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1967 == Reference == https://dl.acm.org/doi/pdf/10.1145/363282.363315")
- 12:18, 15 February 2023 Admin talk contribs created page Wells ( All permutations) (Created page with "== Time Complexity == $O({1})$ per permutation == Space Complexity == $O(n)$ auxiliary words (O(n)-sized array for t_k's necessary) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1961 == Reference == https://www.jstor.org/stable/2004229#metadata_info_tab_contents")
- 12:18, 15 February 2023 Admin talk contribs created page Divide and Conquer ( Minimum value in each row of an implicitly-defined totally monotone matrix) (Created page with "== Time Complexity == $O(m*log(n)$) == Space Complexity == $O(log(n)$) auxiliary? words (Need to keep track of the specific indices where the minimums occur, up to depth log(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://link.springer.com/article/10.1007/BF01840359")
- 12:18, 15 February 2023 Admin talk contribs created page Micali, Vazirani (general graph Maximum cardinality matching) (Created page with "== Time Complexity == $O(V^{0.5} E)$ == Space Complexity == $O(E)$ auxiliary? words (Manipulates a constant number of graphs? Contractions can be kept track of in O(E) space) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1980 == Reference == https://ieeexplore.ieee.org/document/4567800")
- 12:18, 15 February 2023 Admin talk contribs created page Blossom Algorithm (general graph Maximum cardinality matching) (Created page with "== Time Complexity == $O(V^{2}E)$ == Space Complexity == $O(E)$ auxiliary? words (Manipulates a constant number of graphs? Contractions can be kept track of in O(E) space) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1961 == Reference == https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/paths-trees-and-flowers/08B492B72...")
- 12:18, 15 February 2023 Admin talk contribs created page Alt, Blum, Mehlhorn, Paul (bipartite graph Maximum cardinality matching) (Created page with "== Time Complexity == $O(V^{1.5}*(E/logV)$^{0.5}) == Space Complexity == $O(E)$ auxiliary? words (Uses constant number of O(E)-sized data structures in pseudocode of algorithm) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1991 == Reference == https://www.sciencedirect.com/science/article/pii/002001909190195N")
- 12:18, 15 February 2023 Admin talk contribs created page Masek, Paterson (Edit sequence, constant-size alphabet Sequence Alignment) (Created page with "== Time Complexity == $O(mn/log(n)$) == Space Complexity == $O(mn/log(n)$) words (https://www.sciencedirect.com/science/article/pii/0022000080900021?via%3Dihub) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://www.sciencedirect.com/science/article/pii/0022000080900021?via%3Dihub")
- 12:18, 15 February 2023 Admin talk contribs created page Wagner-Fischer algorithm (Edit sequence, constant-size alphabet Sequence Alignment) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$ words (https://dl.acm.org/doi/10.1145/360825.360861) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://dl.acm.org/doi/abs/10.1145/321796.321811")
- 12:18, 15 February 2023 Admin talk contribs created page Wagner-Fischer algorithm (Edit distance, constant-size alphabet Sequence Alignment) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m)$ words (Easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://dl.acm.org/doi/abs/10.1145/321796.321811")
- 12:18, 15 February 2023 Admin talk contribs created page Wu and Manber, Fuzzy String Matching ( String Search) (Created page with "== Time Complexity == $O(nk \lceil m/w \rceil)$ == Space Complexity == $O(ms + k \lceil m/w \rceil)$ (https://dl.acm.org/doi/pdf/10.1145/135239.135244) == Description == == Approximate? == Approximate Approximation Factor: Levensthein Distance = k == Randomized? == No, deterministic == Model of Computation == not mentioned == Year == 1992 == Reference == https://dl.acm.org/doi/pdf/10.1145/135239.135244")
- 12:18, 15 February 2023 Admin talk contribs created page Focused D* ( Informed Search) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.8257")
- 12:18, 15 February 2023 Admin talk contribs created page D* Lite ( Informed Search) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://doi.org/10.1109%2Ftro.2004.838026")
- 12:18, 15 February 2023 Admin talk contribs created page Shi 2009 (NAE 3SAT Boolean Satisfiability) (Created page with "== Time Complexity == $O({12}m*t_extract + {2}m*t_discard + {2}n*t_append + (n+{2}m)$*t_merge + (n-{1})*t_amplify) == Space Complexity == $O(n)$ tubes or $O({2}^n)$ library strands (https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5211463) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Adelman-Lipton == Year == 2009 == Reference == https://ieeexplore.ieee.org/abstract/document/52...")
- 12:18, 15 February 2023 Admin talk contribs created page Anytime Dynamic A* (ADA*) ( Informed Search) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://www.ri.cmu.edu/publications/anytime-dynamic-a-an-anytime-replanning-algorithm/")
- 12:18, 15 February 2023 Admin talk contribs created page Hertli (Modified PPSZ) (4SAT Boolean Satisfiability) (Created page with "== Time Complexity == $O({1.46899}^n)$ == Space Complexity == $O(kn)$ words (Not sure, please look) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2014 == Reference == https://epubs.siam.org/doi/abs/10.1137/120868177")
- 12:18, 15 February 2023 Admin talk contribs created page Hertli (Modified PPSZ) (3SAT Boolean Satisfiability) (Created page with "== Time Complexity == $O({1.30704}^n)$ == Space Complexity == $O(kn)$ words (Not sure, please look) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2014 == Reference == https://epubs.siam.org/doi/abs/10.1137/120868177")
- 12:18, 15 February 2023 Admin talk contribs created page Paturi, Pudlák, Saks, Zane (PPSZ) 2005 (k-SAT Boolean Satisfiability) (Created page with "== Time Complexity == O^*({2}^{n-cn/k}) == Space Complexity == $O(kn)$ words (Derived in notes) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2005 == Reference == https://dl.acm.org/doi/abs/10.1145/1066100.1066101")
- 12:18, 15 February 2023 Admin talk contribs created page Lewis 1978 (Renamable Horn Boolean Satisfiability) (Created page with "== Time Complexity == $O(mn^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1978 == Reference == https://dl.acm.org/doi/10.1145/322047.322059")
- 12:18, 15 February 2023 Admin talk contribs created page Quantum Adiabatic Algorithm (QAA) (CNF-SAT Boolean Satisfiability) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(poly(n)$) qubits () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Quantum == Year == 2001 == Reference == https://arxiv.org/pdf/quant-ph/0001106.pdf")
- 12:17, 15 February 2023 Admin talk contribs created page WalkSAT (CNF-SAT Boolean Satisfiability) (Created page with "== Time Complexity == $O(n*mt*mf)$ == Space Complexity == $O(n)$ (same as above) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 1994 == Reference == https://www.aaai.org/Papers/AAAI/1994/AAAI94-051.pdf")
- 12:17, 15 February 2023 Admin talk contribs created page GSAT (CNF-SAT Boolean Satisfiability) (Created page with "== Time Complexity == $O(n*mt*mf)$ == Space Complexity == $O(n)$ (derived in notes) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 1992 == Reference == http://www.cs.cornell.edu/selman/papers/pdf/92.aaai.gsat.pdf")
- 12:17, 15 February 2023 Admin talk contribs created page Conflict-Driven Clause Learning (CDCL) (CNF-SAT Boolean Satisfiability) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://ieeexplore.ieee.org/document/769433")
- 12:17, 15 February 2023 Admin talk contribs created page Davis-Putnam-Logemann-Loveland Algorithm (DPLL) (CNF-SAT Boolean Satisfiability) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ Binary Search Tree (https://en.wikipedia.org/wiki/DPLL_algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1961 == Reference == https://dl.acm.org/doi/10.1145/368273.368557")
- 12:17, 15 February 2023 Admin talk contribs created page Zwick 2002 (Directed, Unweighted All-Pairs Shortest Paths (APSP)) (Created page with "== Time Complexity == $O(V^{2.575})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference == https://dl.acm.org/doi/abs/10.1145/567112.567114")
- 12:17, 15 February 2023 Admin talk contribs created page Johnson's algorithm (Directed, Weighted (Arbitrary weights) All-Pairs Shortest Paths (APSP)) (Created page with "== Time Complexity == $O(V^{2} log V + VE)$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 1977 == Reference == https://dl.acm.org/doi/10.1145/321992.321993")
- 12:17, 15 February 2023 Admin talk contribs created page Binary representation search with matrix multiplication (Unweighted Graph Diameter) (Created page with "== Time Complexity == $O(V^omega log(V)$) where omega is the exponent on matrix multiplication == Space Complexity == $O(V^{2} logV)$ words (storing all the matrices) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 12:17, 15 February 2023 Admin talk contribs created page Sparse APSP algorithm (Arbitrary edge weights, Sparse graph Graph Diameter) (Created page with "== Time Complexity == $O(V^{2}logV+VE)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 12:17, 15 February 2023 Admin talk contribs created page Dense APSP algorithm (Arbitrary edge weights, Dense graph Graph Diameter) (Created page with "== Time Complexity == $O(V^{3} / {2}^(logV)$^{0.5}) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 12:17, 15 February 2023 Admin talk contribs created page Longest distance first (LDF) page replacement algorithm (Online Page Replacements) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + information related to position of pages) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2017 == Reference == https://www.researchgate.net/profile/Gyanendra-Kumar-3/publication/319467661_A_Novel_Longest_Distance_First_Page_Replacement_Algorithm/links/59b209f1aca2728472d146...")
- 12:17, 15 February 2023 Admin talk contribs created page ARIES (Steal, No-Force Recovery) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? words (Uses write-ahead logging, so keeps track of transaction log, whose entries may be augmented with O(1) more information each. During recovery, needs to keep track of variable/page states) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == https://dl.acm.org/doi/10.1145/128765.128770")
- 12:17, 15 February 2023 Admin talk contribs created page Not frequently used (NFU) (Online Page Replacements) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference counters only) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Aging (Online Page Replacements) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference counters only) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Random (Online Page Replacements) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(k)$? words (Need to keep track of cache?) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Least recently used (Online Page Replacements) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + info related to time last referenced for each of k pages) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Second-chance (Online Page Replacements) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference bits only) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Clock (Online Page Replacements) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference bits only (plus iterator)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page First-in, first-out (Online Page Replacements) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference bits only) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Not recently used (Online Page Replacements) (Created page with "== Time Complexity == $O(nk)$? == Space Complexity == $O(k)$ words (Need to keep track of cache + reference bits only) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page The theoretically optimal page replacement algorithm (Offline Page Replacements) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(k)$ words (Need to keep track of cache; linear scan for searching for page not being used for the longest only requires O(1) auxiliary space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Banker's Algorithm (Deadlock Avoidance Deadlock avoidance) (Created page with "== Time Complexity == $O(mn^{2})$ == Space Complexity == $O(mn)$ words (Main space-consuming arrays needed include "Max," "Allocation," and "Need," which are all n*m arrays. Other arrays are either O(n) or O(m)-sized) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1966 == Reference == https://www.cs.utexas.edu/users/EWD/ewd01xx/EWD108.PDF")
- 12:17, 15 February 2023 Admin talk contribs created page Multilevel queue scheduling (Unweighted Interval Scheduling, Online?? Interval Scheduling) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above; also level information for each task) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Work-conserving schedulers (Unweighted Interval Scheduling, Online?? Interval Scheduling) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Round-robin scheduling (Unweighted Interval Scheduling, Online?? Interval Scheduling) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page First come, first served (Unweighted Interval Scheduling, Online?? Interval Scheduling) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Shortest remaining time first (Unweighted Interval Scheduling, Online?? Interval Scheduling) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Priority scheduling (Unweighted Interval Scheduling, Online?? Interval Scheduling) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (Keep track of (sorted, based on criteria) list of (unscheduled, running, etc.; just un-done) tasks, along with machine statuses) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page $O(n\log n)$ Dynamic Programming (Weighted Activity Selection Problem Interval Scheduling) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Keep track of answers to O(n) subproblems (cache), and sorted list of intervals) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page $O(n^2)$ Dynamic Programming (Weighted Activity Selection Problem Interval Scheduling) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Keep track of answers to O(n) subproblems (cache), and sorted list of intervals) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Fixed priority shortest job first (Unweighted Interval Scheduling, Online?? Interval Scheduling) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n+k)$? words (Keep track of (sorted, based on criteria) list of (unscheduled, running, etc.; just un-done) tasks, along with machine statuses and task priorities) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page $O(n^3)$ Dynamic Programming (Weighted Activity Selection Problem Interval Scheduling) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Keep track of answers to O(n^2) subproblems (i, j)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Brute force algorithm (Weighted Activity Selection Problem Interval Scheduling) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ words (Need to keep track of which subset is being checked) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Sthele, Zimmermann (Greatest Common Divisor Greatest Common Divisor) (Created page with "== Time Complexity == $O(n log^{2} n log log n)$ == Space Complexity == $O(n)$?? bits (Depends on Schonhage-Strassen multiplication) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? words size O(1) == Year == 2006 == Reference == https://hal.inria.fr/file/index/docid/71533/filename/RR-5050.pdf")
- 12:17, 15 February 2023 Admin talk contribs created page Binary GCD algorithm (Greatest Common Divisor Greatest Common Divisor) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ bits (Store only the current values being iterated on) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? words size O(1) == Year == 1967 == Reference == https://arxiv.org/abs/0910.0095")
- 12:17, 15 February 2023 Admin talk contribs created page Euclid's algorithm (Greatest Common Divisor Greatest Common Divisor) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ bits (Store only the current values being iterated on) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? words size O(1) == Year == -300 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Lehmer's GCD algorithm (Greatest Common Divisor Greatest Common Divisor) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ bits (Store only the current values being iterated on, and an O(1)-sized matrix with O(n)-bit numbers) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? words size O(1) == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Calvetti, Reichel (2-D Polynomial Interpolation Polynomial Interpolation) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? words ((maybe similar to the other O(n^2) algorithms?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1993 == Reference == https://link.springer.com/article/10.1007/BF01990529")
- 12:17, 15 February 2023 Admin talk contribs created page Bjorck (2-D Polynomial Interpolation Polynomial Interpolation) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (https://academic.oup.com/imajna/article/8/4/473/758789?login=true) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1970 == Reference == https://www.jstor.org/stable/2004623?origin=crossref&seq=5#metadata_info_tab_contents")
- 12:17, 15 February 2023 Admin talk contribs created page Higham (2-D Polynomial Interpolation Polynomial Interpolation) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (https://academic.oup.com/imajna/article/8/4/473/758789?login=true) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1988 == Reference == https://academic.oup.com/imajna/article/8/4/473/758789?login=true")
- 12:17, 15 February 2023 Admin talk contribs created page Gaussian elimination (2-D Polynomial Interpolation Polynomial Interpolation) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Requires computation of inverse of O(n^2)-sized Vandermonde matrix) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == -150 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Rijndael / AES (Block Ciphers Block Ciphers) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? bits (Network generally operates on the O(n) bits over O(k) rounds, each round having roughly the same structure (so structure of rounds require O(1) bits to describe)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2001 == Reference == https://csrc.nist.gov/csrc/media/projects/cryptographic-standards-and-guid...")
- 12:17, 15 February 2023 Admin talk contribs created page Blowfish (Block Ciphers Block Ciphers) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? bits (Network has a constant number of rounds and operates on O(n) bits, thus structure should require O(n) bits to describe) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://link.springer.com/chapter/10.1007/3-540-58108-1_24")
- 12:17, 15 February 2023 Admin talk contribs created page RC5 (Block Ciphers Block Ciphers) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(k+rw)$? bits (Requires additional O(k/w)-length array of O(w)-size words (temporary working array) and O(r)-length array of O(w)-size words, as key-independent pseudorandom array.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1994 == Reference == https://link.springer.com/chapter/10.1007/3-540-60590-8_7")
- 12:17, 15 February 2023 Admin talk contribs created page IDEA (Block Ciphers Block Ciphers) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? bits ((^see above)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == NA")
- 12:17, 15 February 2023 Admin talk contribs created page Lucifer / DES (Block Ciphers Block Ciphers) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? bits (Network has a constant number of rounds and operates on O(n) bits, thus structure should require O(n) bits to describe) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == NA")
- 12:17, 15 February 2023 Admin talk contribs created page Newton's method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store current estimate x_i and the derivative f' (assuming this takes O(1) space); iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1669 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Secant method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store previous 2 estimates x_i and x_{i-1}; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == -1400 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Regula Falsi method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == -200 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Bisection method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == -150 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Shamir's scheme ( Secret Sharing) (Created page with "== Time Complexity == $O(t^{2})$ for secret computation? (requires polynomial interpolation) == Space Complexity == $O({1})$ per person, $O(t^{2})$ to figure out secret? words (Each person only needs to keep track of a single point (O(1) info); figuring out secret depends on polynomial interpolation algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Refere...")
- 12:17, 15 February 2023 Admin talk contribs created page Blakley's scheme ( Secret Sharing) (Created page with "== Time Complexity == $O(t^{3})$ for secret computation? (requires linear solver) == Space Complexity == $O(t)$ per person, $O(t^{2})$ to figure out secret words (Each person needs to keep track of coefficients of hyperplane; figuring out secret requires O(t) hyperplanes, with O(t) coefficients) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page BLAKE2 (Optional Key? One-Way Hash Functions) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary? bits (Generally processes the message in O(1)-sized chunks; parameters into the "compress" function are also technically O(1)-sized) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2012 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page SHA-2 (Unkeyed Hash Functions One-Way Hash Functions) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary? bits (Based off of Merkel-Damgard construction (see MD5)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2001 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page SHA-3 (Unkeyed Hash Functions One-Way Hash Functions) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(b+d)$ auxiliary? bits (only need constant padding, O(b)-bit "absorb" state being manipulated, constant-sized non-linear functions (i.e. operating on O(1) bits), and O(d)-sized "squeezed" state being manipulated. In practice b, d are O(1)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Whirlpool ( One-Way Hash Functions) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary? bits (Based off of Merkel-Damgard construction (see MD5)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page RIPEMD-160 (Unkeyed Hash Functions One-Way Hash Functions) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary? bits (Likely based off of Merkel-Damgard construction (see MD5)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1996 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Bcrypt (Unkeyed Hash Functions One-Way Hash Functions) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary?? bits (generally operates in the O(1) scheme) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page SHA-1 (Unkeyed Hash Functions One-Way Hash Functions) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary? bits (Based off of Merkel-Damgard construction (see MD5)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page MD5 (Unkeyed Hash Functions One-Way Hash Functions) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary? bits (only need constant padding, 128-bit state being manipulated, and constant-sized non-linear functions (i.e. operating on O(1) bits). Also based off of Merkle-Damgard construction) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Naive Implementation ( Integral Equations) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1800 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Rabin Karp (The Frequent Words Problem The Frequent Words Problem) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(max(n, sigma^k)$) auxiliary? words (Keep track of counts on at most n-k+1 or sigma^k words) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Naive solution (The Frequent Words Problem The Frequent Words Problem) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(max(n, sigma^k)$) auxiliary words (Keep track of counts on at most n-k+1 or sigma^k words) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Hanoi graph (Tower of Hanoi Tower of Hanoi) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == bits () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2008 == Reference == https://books.google.com/books/about/Topics_in_Graph_Theory.html?id=pSv3XotPCQgC")
- 12:17, 15 February 2023 Admin talk contribs created page Gray-code based (Tower of Hanoi Tower of Hanoi) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ auxiliary bits (Need to keep track of an n-bit counter for Gray codes) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == NA")
- 12:17, 15 February 2023 Admin talk contribs created page Non-recursion based (Tower of Hanoi Tower of Hanoi) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ auxiliary bits (Only need to keep track of current configuration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == NA")
- 12:17, 15 February 2023 Admin talk contribs created page Recursion based (Tower of Hanoi Tower of Hanoi) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n*log n)$ auxiliary bits (Need to keep track of an O(n)-sized recursive stack, each entry requiring O(log n) space (i.e. which tower size to manipulate)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == NA")
- 12:17, 15 February 2023 Admin talk contribs created page Iteration based (Tower of Hanoi Tower of Hanoi) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ auxiliary bits (Only need to keep track of current configuration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1883 == Reference == NA")
- 12:17, 15 February 2023 Admin talk contribs created page Naive solution ( Frequent Words with Mismatches Problem) (Created page with "== Time Complexity == $O(n*f_{bin}(sigma-{1}, k, d)$) where f_{bin}(x, y, z) = sum_{i=0}^z C(y, i)*x^i == Space Complexity == $O(max(n*f_{bin}(sigma-{1}, k, d)$, sigma^k)) auxiliary where f_{bin}(x, y, z) = sum_{i=0}^z C(y, i)*x^i words (Keep track of counts on at most that many words) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Rivin, Zabih (Counting Solutions n-Queens Problem) (Created page with "== Time Complexity == $O({8}^n*poly(n)$) == Space Complexity == $O({8}^n*n^{2})$ words (http://www.cs.cornell.edu/~rdz/Papers/RZ-IPL92.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == http://www.cs.cornell.edu/~rdz/Papers/RZ-IPL92.pdf")
- 12:17, 15 February 2023 Admin talk contribs created page Naive Solution (Median String Problem with Unbounded Alphabets Median String Problem) (Created page with "== Time Complexity == {2}^$O(n)$ == Space Complexity == $O(n)$ auxiliary words (Keep track of current string being checked, current best string, and Levenshtein distances (which can be computed recursively using O(n) space)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1965 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Gunther Determinants solution (Counting Solutions; Constructing solutions n-Queens Problem) (Created page with "== Time Complexity == $O(n!)$ == Space Complexity == $O(n!)$ ? words (Seems like this one lists out all of the terms in the discriminant; presumably there is a better way but that amounts to the naive algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1874 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Nauck (Counting Solutions; Constructing solutions n-Queens Problem) (Created page with "== Time Complexity == $O(n!)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1850 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Dijkstra (Counting Solutions; Constructing solutions n-Queens Problem) (Created page with "== Time Complexity == $O(n!)$ == Space Complexity == $O(n)$ words (Keep track of current configuration being tested and restrictions on where next queen can be placed, along with current count) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://dl.acm.org/citation.cfm?id=1243380")
- 12:17, 15 February 2023 Admin talk contribs created page Naive + 1 queen per row restriction (Counting Solutions; Constructing solutions n-Queens Problem) (Created page with "== Time Complexity == $O(n!)$ == Space Complexity == $O(n)$ words (Keep track of current configuration being tested, along with current count) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1850 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Naive Algorithm (Counting Solutions; Constructing solutions n-Queens Problem) (Created page with "== Time Complexity == $O(n^n)$ == Space Complexity == $O(n)$ words (Keep track of current configuration being tested, along with current count) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1848 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Outside-In algorithm (Turnpike Problem Turnpike Problem) (Created page with "== Time Complexity == $O({2}^n nlogn)$ == Space Complexity == $O(n)$ words (Seems like this just needs to keep track of current configuration being tested) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == NA")
- 12:17, 15 February 2023 Admin talk contribs created page Gries, Martin (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Generally keeps track of O(1) information for every pair (u, v) of vertices? and not much additional information needed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://www.sciencedirect.com/science/article/pii/0167642389900397")
- 12:17, 15 February 2023 Admin talk contribs created page Aho, Garey & Ullman (Transitive Reduction Problem of Directed Graphs Transitive Reduction Problem) (Created page with "== Time Complexity == $O(n^omega)$ where omega is the exponent on boolean matrix multiplication == Space Complexity == $O(n^{2})$ words (see (boolean) matrix multiplication) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://epubs.siam.org/doi/pdf/10.1137/0201008")
- 12:17, 15 February 2023 Admin talk contribs created page Guibas, Sedgewick Red-Black Tree ( Self-Balancing Trees Search) (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 == 1972 == Reference == https://ieeexplore.ieee.org/document/4567957")
- 12:17, 15 February 2023 Admin talk contribs created page Hopcroft 2-3 Tree ( Self-Balancing Trees Search) (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 == 1970 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Guibas, Sedgewick Red-Black Tree ( Self-Balancing Trees Deletion) (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 == 1972 == Reference == https://ieeexplore.ieee.org/document/4567957")
- 12:17, 15 February 2023 Admin talk contribs created page Hopcroft 2-3 Tree ( Self-Balancing Trees Deletion) (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 == 1970 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Guibas, Sedgewick Red-Black Tree ( Self-Balancing Trees Insertion) (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 == 1972 == Reference == https://ieeexplore.ieee.org/document/4567957")
- 12:17, 15 February 2023 Admin talk contribs created page Hopcroft 2-3 Tree ( Self-Balancing Trees Insertion) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (Each node being changed requires constant auxiliary space to make changes; can reuse space across nodes being changed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Bayer, McCreight B-Tree ( Self-Balancing Trees Creation) (Created page with "== Time Complexity == $O(n*b*log(n)$/log(b))? == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Tarjan Splay Tree ( Self-Balancing Trees Creation) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Hopcroft 2-3 Tree ( Self-Balancing Trees Creation) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Guibas, Sedgewick Red-Black Tree ( Self-Balancing Trees Creation) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://ieeexplore.ieee.org/document/4567957")
- 12:17, 15 February 2023 Admin talk contribs created page AVL Tree ( Self-Balancing Trees Creation) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference ==")
- 12:17, 15 February 2023 Admin talk contribs created page Pollard's kangaroo algorithm (Discrete Logarithm Over Finite Fields Logarithm Calculations) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O({1})$ words (Stores a constant number of O(n)-bit values (a, b, x_i, d, x_N, y_i, d_i) per iteration; assumes that the pseudorandom map is part of the input) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1978 == Reference == https://www.ams.org/mcom/1978-32-143/S0025-5718-1978-0491431-9/S0025-5718-1978-0491431...")
- 12:17, 15 February 2023 Admin talk contribs created page Pollard's rho algorithm (Discrete Logarithm Over Finite Fields Logarithm Calculations) (Created page with "== Time Complexity == $O({2}^{(n/{2})})$ == Space Complexity == $O({1})$ words (Stores a constant number of O(n)-bit values per iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1978 == Reference == https://www.ams.org/mcom/1978-32-143/S0025-5718-1978-0491431-9/S0025-5718-1978-0491431-9.pdf")
- 12:17, 15 February 2023 Admin talk contribs created page Pohlig-Hellman (Discrete Logarithm Over Finite Fields Logarithm Calculations) (Created page with "== Time Complexity == $O({2}^{\sqrt{n}})$, only for primes; does much better for composites == Space Complexity == $O({2}^{\sqrt{n}})$ (though only for primes) words (A step in the algorithm involves using baby-steps giant-steps to compute discrete logs; the rest of the algorithm (including CRT and repeated powers) isn't as intensive) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM ==...")
- 12:17, 15 February 2023 Admin talk contribs created page Number Field Sieve (NFS) (Discrete Logarithm Over Finite Fields Logarithm Calculations) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n^{2/3})$ bits (http://www.ams.org/notices/199612/pomerance.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1990 == Reference == http://www.ams.org/notices/199612/pomerance.pdf")
- 12:17, 15 February 2023 Admin talk contribs created page Index calculus algorithm (Discrete Logarithm Over Finite Fields, F q Logarithm Calculations) (Created page with "== Time Complexity == $O(e^{(\sqrt({2}) \sqrt(n*logn))})$ == Space Complexity == $O(n+r^{2})$? bits (See Dixon's algorithm for factoring integers; also works with an O(r)-by-O(r) sized matrix (to obtain discrete logs of primes in factor base)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == RAM? == Year == 1922 == Reference == NA")
- 12:17, 15 February 2023 Admin talk contribs created page Function Field Sieve (FFS) (Discrete Logarithm Over Finite Fields Logarithm Calculations) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n^{2/3})$? bits (Derived: same space as Number Field Sieve?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://www.sciencedirect.com/science/article/pii/S0890540198927614")
- 12:17, 15 February 2023 Admin talk contribs created page Baby-step Giant-step (Discrete Logarithm Over Finite Fields Logarithm Calculations) (Created page with "== Time Complexity == $O({2}^{\sqrt{n}})$ == Space Complexity == $O({2}^{\sqrt{n}})$ words (Derived: Uses a hash table of this size) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://doi.org/10.1090/pspum/020")
- 12:17, 15 February 2023 Admin talk contribs created page Trial Multiplication (Discrete Logarithm Over Finite Fields Logarithm Calculations) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O({1})$ words (Derived: Each power $k$ that you try in the brute force search is size $O(\log n)$, which is $O(1)$ when considering $O(\log n)$ size words. Only need to keep track of one at a time.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == NA")
- 12:17, 15 February 2023 Admin talk contribs created page Rautiainen, Marschall (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (Created page with "== Time Complexity == $O(|V | + m|E|)$ == Space Complexity == $O(mV)$ words (Derived: algorithm uses a V-sized array of bitvectors each of which is of length m, and also uses a priority queue which has at most V elements. The precomputed pattern bitvectors also takes up O(V * m) space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2019 == Reference == https://www.ncb...")
- 12:17, 15 February 2023 Admin talk contribs created page Jain, Chang (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (Created page with "== Time Complexity == $O(|V | + m|E|)$ == Space Complexity == $O(V)$ words (https://www.biorxiv.org/content/10.1101/522912v1.full.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2019 == Reference == https://www.biorxiv.org/content/10.1101/522912v1.full.pdf")
- 12:17, 15 February 2023 Admin talk contribs created page Rautiainen and Marschall (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (Created page with "== Time Complexity == $O(|V | + m|E|)$ == Space Complexity == $O(\sqrt(m)|V|)$ words (same paper) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2017 == Reference == https://www.biorxiv.org/content/10.1101/216127v1")
- 12:17, 15 February 2023 Admin talk contribs created page V-ALIGN (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (Created page with "== Time Complexity == $O(m|V |E|)$ == Space Complexity == $O(mV)$ words (https://www.biorxiv.org/content/10.1101/124941v1.full) == Description == Dynamic Programming == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2018 == Reference == https://www.biorxiv.org/content/10.1101/124941v1.full")
- 12:17, 15 February 2023 Admin talk contribs created page HybridSpades (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (Created page with "== Time Complexity == $O(m(|V | log(m|V |)$ + |E|)) == Space Complexity == $O(m*(V+E)$) words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/26589280")
- 12:17, 15 February 2023 Admin talk contribs created page Navarro (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (Created page with "== Time Complexity == $O(n(|V | + |E|)$) == Space Complexity == $O(V)$ words (same paper) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://www.sciencedirect.com/science/article/pii/S0304397599003333")
- 12:17, 15 February 2023 Admin talk contribs created page Amir et al. (Sequence-to-Graph Alignment Sequence-to-Graph Alignment) (Created page with "== Time Complexity == $O(m(|n | log |m | + |E|)$) == Space Complexity == $O(mn)$ words (https://reader.elsevier.com/reader/sd/pii/S0304397599003333?token=C0E6BDF7BA98CD5C338EDB86675CB3A29AF44F5B046E169EE0F115788255757C815F0F0307EAF080CDF9A9DE7AA37764) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1997 == Reference == https://link.springer.com/chapter/10.1007/3-540-633...")
- 12:17, 15 February 2023 Admin talk contribs created page PSLQ algorithm (Integer Relation Integer Relation) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Derived: Uses multiple nxn auxiliary matrices) == Description == Partial Sum of Squares using QR decomposition == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == https://www.ams.org/journals/mcom/1999-68-225/S0025-5718-99-00995-3/S0025-5718-99-00995-3.pdf")
- 12:17, 15 February 2023 Admin talk contribs created page PSOS algorithm (Integer Relation Integer Relation) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Derived: Uses multiple nxn auxiliary matrices) == Description == Partial Sum of Squares == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1988 == Reference == https://www.ams.org/journals/mcom/1989-53-188/S0025-5718-1989-0979934-9/S0025-5718-1989-0979934-9.pdf")
- 12:17, 15 February 2023 Admin talk contribs created page LLL algorithm (Integer Relation Integer Relation) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n^{2})$ words (Derived: Uses n auxiliary vectors each of length n, as well as an nxn matrix) == Description == Lattice-based == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1982 == Reference == https://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1982f/art.pdf")
- 12:17, 15 February 2023 Admin talk contribs created page Ferguson–Forcade algorithm (Integer Relation Integer Relation) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Derived: Uses auxiliary $n\times n$ matrices) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == https://www.ams.org/journals/bull/1979-01-06/S0273-0979-1979-14691-3/S0273-0979-1979-14691-3.pdf")
- 12:17, 15 February 2023 Admin talk contribs created page Bareiss algorithm with fast multiplication (Determinant of Matrices with Integer Entries Determinant of Matrices with Integer Entries) (Created page with "== Time Complexity == $O(n^{4}L(log(n)$ + L)log(log(n) + L)) == Space Complexity == $O(n^{2}(n*log(n)$+nL)) bits (Keeps track of $O(n^2)$ entries that have absolute value at most $O(n^{(n/2)}2^{(nL)})$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? (without O(1) multiplication) == Year == 1968 == Reference == -")
- 12:17, 15 February 2023 Admin talk contribs created page Bareiss algorithm (Determinant of Matrices with Integer Entries Determinant of Matrices with Integer Entries) (Created page with "== Time Complexity == $O(n^{5}L^{2} (log(n)$^{2} + L^{2})) == Space Complexity == $O(n^{2}(n*log(n)$+nL)) bits (Keeps track of $O(n^2)$ entries that have absolute value at most $O(n^{(n/2)}2^{(nL)})$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? (without O(1) multiplication) == Year == 1968 == Reference == https://www.ams.org/journals/mcom/1968-22-103/S0025-5718-1968-0226829-0...")
- 12:16, 15 February 2023 Admin talk contribs created page Ruchansky (Minimum Wiener Connector problem Wiener Index) (Created page with "== Time Complexity == $O(q(m*log(n)$+n*log^{2}(n))) == Space Complexity == $O(q(m+n*log(n)$)? words (Keeps track of $O(qm)$ shortest-path distances and $O(q*log(n))$ approximate Steiner trees, each of size $O(n)$) == Description == == Approximate? == Approximate Approximation Factor: O(1) == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference == https://arxiv.org/abs/1504.00513")
- 12:16, 15 February 2023 Admin talk contribs created page Dunning; Gupta & Silberholz (Maximum Cut, Approximate Maximum Cut) (Created page with "== Time Complexity == $O(VE)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2018 == Reference == https://pubsonline.informs.org/doi/epdf/10.1287/ijoc.2017.0798")
- 12:16, 15 February 2023 Admin talk contribs created page LEE Y.; KIM H. S.; LEE S 2002 (Mesh Parameterization Mesh Parameterization) (Created page with "== Time Complexity == $O(n log^{3}n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0097849302001231")
- 12:16, 15 February 2023 Admin talk contribs created page PINKALL U.; POLTHIER K 1993 (Mesh Parameterization Mesh Parameterization) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1993 == Reference == http://www.cs.jhu.edu/~misha/Fall09/Pinkall93.pdf")
- 12:16, 15 February 2023 Admin talk contribs created page FLOATER 1997 (Mesh Parameterization Mesh Parameterization) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == http://www.cs.jhu.edu/~misha/Fall09/Floater97.pdf")
- 12:16, 15 February 2023 Admin talk contribs created page ECK M.; DEROSE T.; DUCHAMP T.; 1995 (Mesh Parameterization Mesh Parameterization) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1995 == Reference == https://dl.acm.org/doi/10.1145/218380.218440")
- 12:16, 15 February 2023 Admin talk contribs created page B. I. Kvasov 2000 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2000 == Reference ==")
- 12:16, 15 February 2023 Admin talk contribs created page P. Costantini; B. I. Kvasov; and C. Manni 1999 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (Created page with "== Time Complexity == $O(n^{5} logK)$ == Space Complexity == $O(n)$? words (Derived: Pentadiagonal matrix in the linear system only requires O(n) space) == Description == Pentadiagonal linear system == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://link.springer.com/article/10.1023/A:1018988312596")
- 12:16, 15 February 2023 Admin talk contribs created page V. I. Paasonen 1968 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (Created page with "== Time Complexity == $O(n^{5} logK)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1968 == Reference ==")
- 12:16, 15 February 2023 Admin talk contribs created page V. A. Lyul’ka and I. E. Mikhailov 2003 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2003 == Reference == http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=zvmmf&paperid=943&option_lang=eng")
- 12:16, 15 February 2023 Admin talk contribs created page V. A. Lyul’ka and A. V. Romanenko 1994 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (Created page with "== Time Complexity == $O(n^{5})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1994 == Reference == https://www.mathnet.ru/eng/zvmmf2544")
- 12:16, 15 February 2023 Admin talk contribs created page Kvasov 2006 (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (Created page with "== Time Complexity == $O(n^{3} log^{2}K)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2008 == Reference == https://link.springer.com/article/10.1134/S0965542508040039")
- 12:16, 15 February 2023 Admin talk contribs created page Adaptive Duplicate Detection Algorithm (ADD) (Duplicate Elimination Duplicate Elimination) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O({1})$ words (Derived: For SVM, only need to store a constant number of support vectors) == Description == SVM string similarity == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://dl.acm.org/doi/10.1145/956750.956759")
- 12:16, 15 February 2023 Admin talk contribs created page Sorted Neighborhood Algorithm (SNA) (Duplicate Elimination Duplicate Elimination) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Derived: store a key for each entry in the "Create Key" phase) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://link.springer.com/article/10.1023/A:1009761603038")
- 12:16, 15 February 2023 Admin talk contribs created page Duplicate Elimination Sorted Neighborhood Algorithm (DE-SNA) (Duplicate Elimination Duplicate Elimination) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference ==")