User contributions for Admin
Jump to navigation
Jump to search
28 April 2023
- 08:4608:46, 28 April 2023 diff hist 0 File:Minimum value in each row of an implicitly-defined totally monotone matrix - Time.png Admin uploaded a new version of File:Minimum value in each row of an implicitly-defined totally monotone matrix - Time.png
10 April 2023
- 09:0009:00, 10 April 2023 diff hist +37 Reduction from 3-OV to k-OV No edit summary current
- 09:0009:00, 10 April 2023 diff hist +33 Reduction from OV to k-OV No edit summary current
- 09:0009:00, 10 April 2023 diff hist +650 N Reduction from Triangle Detection to Disjunctive Reachability Queries in MDPs Created page with "FROM: Triangle Detection TO: Disjunctive Reachability Queries 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: Dis..." current
- 09:0009:00, 10 April 2023 diff hist +12 Reduction from k-Clique to RNA Folding No edit summary Tags: Manual revert Reverted
- 09:0009:00, 10 April 2023 diff hist +12 Reduction from k-Clique to CFG Recognition No edit summary Tag: Manual revert
- 09:0009:00, 10 April 2023 diff hist −12 Reduction from k-Clique to RNA Folding No edit summary Tags: Manual revert Reverted
- 09:0009:00, 10 April 2023 diff hist −12 Reduction from k-Clique to CFG Recognition No edit summary Tags: Manual revert Reverted
- 08:5908:59, 10 April 2023 diff hist +90 Reduction from Triangle Collection* to dynamic 4/3-Diameter No edit summary Tag: Manual revert
- 08:5908:59, 10 April 2023 diff hist −134 Reduction from Triangle Collection* to dynamic 4/3-Diameter No edit summary Tags: Manual revert Reverted
- 08:5908:59, 10 April 2023 diff hist +44 Reduction from Triangle Collection* to dynamic 4/3-Diameter No edit summary Tags: Manual revert Reverted
- 08:5908:59, 10 April 2023 diff hist +92 Reduction from MAX-CNF-SAT to All-Pairs Maximum Flow No edit summary current Tag: Manual revert
- 08:5908:59, 10 April 2023 diff hist −26 Reduction from CNF-SAT to Approximate Reach Centrality No edit summary Tags: Manual revert Reverted
- 08:5908:59, 10 April 2023 diff hist +26 Reduction from CNF-SAT to Approximate Reach Centrality No edit summary Tags: Manual revert Reverted
- 08:5908:59, 10 April 2023 diff hist +251 Reduction from Reach Centrality to Diameter No edit summary Tag: Manual revert
- 08:5808:58, 10 April 2023 diff hist −251 Reduction from Reach Centrality to Diameter No edit summary Tags: Manual revert Reverted
- 08:5808:58, 10 April 2023 diff hist −49 Reduction from Matrix Product to Negative Triangle Detection No edit summary Tags: Manual revert Reverted
- 08:5808:58, 10 April 2023 diff hist +52 Reduction from Matrix Product to Negative Triangle Detection No edit summary Tags: Manual revert Reverted
- 08:5808:58, 10 April 2023 diff hist +7 Reduction from Matrix Product to Negative Triangle Detection No edit summary Tags: Manual revert Reverted
- 08:5808:58, 10 April 2023 diff hist −10 Reduction from Matrix Product to Negative Triangle Detection No edit summary Tags: Manual revert Reverted
- 08:5708:57, 10 April 2023 diff hist +1 Reduction from OV to Edit Distance No edit summary current
- 08:5608:56, 10 April 2023 diff hist −17 Smith (2-dimensional Maximum subarray problem) No edit summary Tags: Manual revert Reverted
- 08:5608:56, 10 April 2023 diff hist +17 Smith (2-dimensional Maximum subarray problem) No edit summary Tags: Manual revert Reverted
- 08:5608:56, 10 April 2023 diff hist +309 N Wen (1-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" current
- 08:5608:56, 10 April 2023 diff hist −9 Gronlund, Pettie (Real 3SUM 3SUM) No edit summary Tags: Manual revert Reverted
- 08:5608:56, 10 April 2023 diff hist +9 Gronlund, Pettie (Real 3SUM 3SUM) No edit summary Tags: Manual revert Reverted
- 08:5608:56, 10 April 2023 diff hist +12 Baran, Demaine, Patrascu (Integer 3SUM 3SUM) No edit summary Tags: Manual revert Reverted
- 08:5608:56, 10 April 2023 diff hist −49 Baran, Demaine, Patrascu (Integer 3SUM 3SUM) No edit summary Tag: Reverted
- 08:5608:56, 10 April 2023 diff hist +6 Baran, Demaine, Patrascu (Integer 3SUM 3SUM) No edit summary Tags: Manual revert Reverted
- 08:5508:55, 10 April 2023 diff hist +31 Baran, Demaine, Patrascu (Integer 3SUM 3SUM) No edit summary Tags: Manual revert Reverted
- 08:5508:55, 10 April 2023 diff hist +22 Gabow (general Maximum-weight matching) No edit summary Tags: Manual revert Reverted
- 08:5508:55, 10 April 2023 diff hist −22 Gabow (general Maximum-weight matching) No edit summary Tags: Manual revert Reverted
- 08:5508:55, 10 April 2023 diff hist +410 N Masek, Paterson (Edit sequence 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" current
- 08:5508:55, 10 April 2023 diff hist +334 N Wagner-Fischer algorithm (Edit sequence 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" current
- 08:5508:55, 10 April 2023 diff hist +303 N Wagner-Fischer algorithm (Edit distance 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" current
- 08:5408:54, 10 April 2023 diff hist −22 Vaidya ( Linear Programming) No edit summary Tags: Manual revert Reverted
- 08:5408:54, 10 April 2023 diff hist +22 Vaidya ( Linear Programming) No edit summary Tags: Manual revert Reverted
- 08:5308:53, 10 April 2023 diff hist 0 Fomin; Gaspers & Saurabh ( No edit summary current Tag: Manual revert
- 08:5308:53, 10 April 2023 diff hist +1 Goldberg & Rao (Parallel) (Integer Maximum Flow Maximum Flow) No edit summary Tag: Manual revert
- 08:5308:53, 10 April 2023 diff hist −1 Goldberg & Rao (Parallel) (Integer Maximum Flow Maximum Flow) No edit summary Tags: Manual revert Reverted
- 08:5308:53, 10 April 2023 diff hist −30 Kathuria, Liu, Sidford ( Maximum Flow) No edit summary Tag: Manual revert
- 08:5308:53, 10 April 2023 diff hist +30 Kathuria, Liu, Sidford ( Maximum Flow) No edit summary Tags: Manual revert Reverted
- 08:5308:53, 10 April 2023 diff hist +2 Chan (Boolean Matrix Multiplication (Combinatorial) Matrix Product) No edit summary current Tag: Manual revert
- 08:5308:53, 10 April 2023 diff hist −2 Chan (Boolean Matrix Multiplication (Combinatorial) Matrix Product) No edit summary Tags: Manual revert Reverted
- 08:5308:53, 10 April 2023 diff hist +9 Bansal, Williams (Boolean Matrix Multiplication (Combinatorial) Matrix Product) No edit summary current Tag: Manual revert
- 08:5208:52, 10 April 2023 diff hist +2 Newton's method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) No edit summary current
- 08:5208:52, 10 April 2023 diff hist +2 Secant method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) No edit summary current
- 08:5208:52, 10 April 2023 diff hist +2 Regula Falsi method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) No edit summary current
- 08:5208:52, 10 April 2023 diff hist +2 Bisection method (Solutions to Nonlinear Equations Solutions to Nonlinear Equations) No edit summary current
- 08:5108:51, 10 April 2023 diff hist −4 Rabin Karp (The Frequent Words Problem The Frequent Words Problem) No edit summary current