User contributions for Admin

15 February 2023

• 10:5510:55, 15 February 2023 diff hist +52‎ Reduction from Matrix Product to Negative Triangle Detection ‎No edit summary
• 10:5510:55, 15 February 2023 diff hist +7‎ Reduction from Matrix Product to Negative Triangle Detection ‎No edit summary
• 10:5510:55, 15 February 2023 diff hist +578‎ N Reduction from Negative Triangle Listing to Negative Triangle Detection ‎ Created page with "FROM: Negative Triangle Listing TO: Negative Triangle Detection == Description == == Implications == if: to-time: $O(n^{3-\epsilon}\log^c M)$ for some $\epsilon > {0}$ and where $M$ is the maxint of $R$<br/>then: from-time: $O(n^{3-\epsilon'}\log^c M)$ for some $\epsilon' > {0}$ for listing $\Delta = O(n^{3-\delta})$ negative triangles with fixed $\delta > {0}$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Betw..." current
• 10:5510:55, 15 February 2023 diff hist +392‎ N Reduction from Negative Triangle Search to Negative Triangle Detection ‎ Created page with "FROM: Negative Triangle Search TO: Negative Triangle Detection == Description == == Implications == if: to-time: $T(n)$ where $T(n)/n$ is decreasing<br/>then: from-time: $O(T(n))$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Lemma 4.1" current
• 10:5510:55, 15 February 2023 diff hist +514‎ N Reduction from Matrix Product to Negative Triangle Detection ‎ Created page with "FROM: Matrix Product TO: Negative Triangle Detection == Description == Generic runtimes for two $n \times n$ matrices == Implications == if: to-time: $T(n)$ where $T(n)/n$ is decreasing<br/>then: from-time: $O(n^{2} \cdot T(n^{1/3})\log W)$ for two $n\times n$ matrices where $W$ is the maxint of $R$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.o..."
• 10:5510:55, 15 February 2023 diff hist +371‎ N Reduction from Negative Triangle Detection to Matrix Product Verification ‎ Created page with "FROM: Negative Triangle Detection TO: Matrix Product Verification == Description == == Implications == if: to-time: $T(n)$<br/>then: from-time: $O(T({2}n))$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 4.1" current
• 10:5510:55, 15 February 2023 diff hist +467‎ N Reduction from BMM to CFG Parsing ‎ Created page with "FROM: BMM TO: CFG Parsing == Description == == Implications == if: to-time: $O(gn^{3-\epsilon})$ for some $\epsilon > {0}$ where $g$ is the size of the CFG and $n$ is the size of the string<br/>then: from-time: $O(n^{3-\epsilon/3})$ where $n \times n$ matrix == Year == 2002 == Reference == L. Lee. 2002. Fast context-free grammar parsing requires fast boolean matrix multiplication. J. ACM 49, 1 (2002), 1–15. https://arxiv.org/abs/cs/0112018" current
• 10:5510:55, 15 February 2023 diff hist +467‎ N Reduction from CFG Parsing to BMM ‎ Created page with "FROM: CFG Parsing TO: BMM == Description == == Implications == if: to-time: $O(n^{3-\epsilon})$ for some $\epsilon > {0}$ where $n \times n$ matrix<br/>then: from-time: $O(gn^{3-\epsilon})$ where $g$ is the size of the CFG == Year == 1975 == Reference == L. G. Valiant. 1975. General context-free recognition in less than cubic time. J. Comput. Syst. Sci. 10 (1975), 308–315. https://www.sciencedirect.com/science/article/pii/S0022000075800468" current
• 10:5510:55, 15 February 2023 diff hist +607‎ N Reduction from CNF-SAT to Multiple Local Alignment ‎ Created page with "FROM: CNF-SAT TO: Multiple Local Alignment == Description == == Implications == if: to-time: $N^{k-\epsilon}$ for some $\epsilon > {0}$ on $k$ binary strings of length $n$ with $k$-wise scoring<br/>then: from-time: ${2}^{(n-\epsilon')}$ for some $\epsilon' > {0}$ == Year == 2014 == Reference == Abboud, Amir, Virginia Vassilevska Williams, and Oren Weimann. "Consequences of faster alignment of sequences." In International Colloquium on Automata, Langu..." current
• 10:5510:55, 15 February 2023 diff hist +421‎ N Reduction from Directed, Weighted APSP to Negative Triangle Detection ‎ Created page with "FROM: Directed, Weighted APSP TO: Negative Triangle Detection == Description == == Implications == if: to-time: $n^{3-\epsilon}$ for some $\epsilon >{0}$<br/>then: from-time: $n^{3-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893" current
• 10:5510:55, 15 February 2023 diff hist +566‎ N Reduction from CNF-SAT to Longest Common Substring with don't cares ‎ Created page with "FROM: CNF-SAT TO: Longest Common Substring with don't cares == Description == == Implications == if: to-time: $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: ${2}^{(n-\epsilon')}$ for some $\epsilon' > {0}$ == Year == 2014 == Reference == Abboud, Amir, Virginia Vassilevska Williams, and Oren Weimann. "Consequences of faster alignment of sequences." In International Colloquium on Automata, Languages, and Programming, pp. 39-51. Springe..." current
• 10:5510:55, 15 February 2023 diff hist +576‎ N Reduction from CNF-SAT to Local Alignment ‎ Created page with "FROM: CNF-SAT TO: Local Alignment == Description == == Implications == if: to-time: $N^{2-\epsilon}$ for some $\epsilon > {0}$ on two binary strings of length $N$<br/>then: from-time: ${2}^{(n-\epsilon')}$ for some $\epsilon' > {0}$ == Year == 2014 == Reference == Abboud, Amir, Virginia Vassilevska Williams, and Oren Weimann. "Consequences of faster alignment of sequences." In International Colloquium on Automata, Languages, and Programming, pp. 39-5..." current
• 10:5510:55, 15 February 2023 diff hist +625‎ N Reduction from 3SUM to Local Alignment ‎ Created page with "FROM: 3SUM TO: Local Alignment == Description == == Implications == if: to-time $N^{2-\delta-\epsilon} for two strings of size $n$ and alphabet of size $n^{1-\delta}$ for some $\espilon > {0}$,$\delta \in ({0},{1})$<br/>then: from-time: $n^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 2014 == Reference == Abboud, Amir, Virginia Vassilevska Williams, and Oren Weimann. "Consequences of faster alignment of sequences." In International Colloquium..." current
• 10:5510:55, 15 February 2023 diff hist +491‎ N Reduction from 3SUM' to Static Dihedral Rotation Queries ‎ Created page with "FROM: 3SUM' TO: Static Dihedral Rotation Queries == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 2003 == Reference == Michael Soss, Jeff Erickson, Mark Overmars, Preprocessing chains for fast dihedral rotations is hard or even impossible, Computational Geometry, Volume 26, Issue 3, 2003, Pages 235-246 https://doi.org/10.1016/S0925..." current
• 10:5510:55, 15 February 2023 diff hist +462‎ N Reduction from Triangles Cover Triangle to 3D Motion Planning ‎ Created page with "FROM: Triangles Cover Triangle TO: 3D Motion Planning == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2" current
• 10:5510:55, 15 February 2023 diff hist +450‎ N Reduction from GeomBase to Planar Motion Planning ‎ Created page with "FROM: GeomBase TO: Planar Motion Planning == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2" current
• 10:5510:55, 15 February 2023 diff hist +460‎ N Reduction from Triangles Cover Triangle to Visible Triangle ‎ Created page with "FROM: Triangles Cover Triangle TO: Visible Triangle == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2" current
• 10:5510:55, 15 February 2023 diff hist +460‎ N Reduction from Visible Triangle to Triangles Cover Triangle ‎ Created page with "FROM: Visible Triangle TO: Triangles Cover Triangle == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2" current
• 10:5510:55, 15 February 2023 diff hist +452‎ N Reduction from GeomBase to Visibility From Infinity ‎ Created page with "FROM: GeomBase TO: Visibility From Infinity == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2" current
• 10:5410:54, 15 February 2023 diff hist +390‎ N Brandes (Weighted Betweenness Centrality (BC)) ‎ Created page with "== Time Complexity == $O(nm + n^{2} \log n)$ == Space Complexity == $O(n + m)$ (https://www.tandfonline.com/doi/abs/10.1080/0022250x.2001.9990249) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == not mentioned == Year == 2000 == Reference == https://www.tandfonline.com/doi/abs/10.1080/0022250x.2001.9990249" current
• 10:5410:54, 15 February 2023 diff hist +375‎ N Brandes (Unweighted Betweenness Centrality (BC)) ‎ Created page with "== Time Complexity == $O(nm)$ == Space Complexity == $O(n + m)$ (https://www.tandfonline.com/doi/abs/10.1080/0022250x.2001.9990249) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == not mentioned == Year == 2000 == Reference == https://www.tandfonline.com/doi/abs/10.1080/0022250x.2001.9990249" current
• 10:5410:54, 15 February 2023 diff hist +328‎ N Thorup (positive integer weights; assumes constant-time multiplication Shortest Path (Undirected graphs)) ‎ Created page with "== Time Complexity == $O(E)$ == Space Complexity == $O(E)$ words (https://dl.acm.org/doi/10.1145/316542.316548) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://dl.acm.org/doi/10.1145/316542.316548" current
• 10:5410:54, 15 February 2023 diff hist +337‎ N Dial's Algorithm (nonnegative integer weights Shortest Path (Directed graphs)) ‎ Created page with "== Time Complexity == $O(E+LV)$ == Space Complexity == $O(V+L)$ words (keep track of vertices and L most recent buckets) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1969 == Reference == https://dl.acm.org/doi/10.1145/363269.363610" current
• 10:5410:54, 15 February 2023 diff hist +432‎ N Khuller, Matias (k-dimensional space, Euclidean metric Closest Pair Problem) ‎ Created page with "== Time Complexity == infinite (can be upper bounded by $O(n^{2})$) == Space Complexity == $O(n)$ words (https://www.sciencedirect.com/science/article/pii/S0890540185710498?via%3Dihub) == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Real RAM == Year == 1995 == Reference == https://www.sciencedirect.com/science/article/pii/S0890540185710498?via%3Dihub" current
• 10:5410:54, 15 February 2023 diff hist +318‎ N Gabow et al, Section 3 (Directed (Optimum Branchings), General MST Minimum Spanning Tree (MST)) ‎ Created page with "== Time Complexity == $O(E+VlogV)$ == Space Complexity == $O(E+V)$ words ((derived in sheet)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1986 == Reference == https://link.springer.com/article/10.1007/BF02579168" current
• 10:5410:54, 15 February 2023 diff hist +360‎ N Tarjan (directed, dense) (Directed (Optimum Branchings), Super Dense MST Minimum Spanning Tree (MST)) ‎ Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == $O(E)$ words (https://onlinelibrary.wiley.com/doi/10.1002/net.3230070103) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://onlinelibrary.wiley.com/doi/10.1002/net.3230070103" current
• 10:5410:54, 15 February 2023 diff hist +343‎ N Gabow, Galil, Spencer (Directed (Optimum Branchings), General MST Minimum Spanning Tree (MST)) ‎ Created page with "== Time Complexity == $O(VlogV+Eloglog(logV/log(E/V + {2})$)) == Space Complexity == $O(E)$ words ((derived in sheet)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://ieeexplore.ieee.org/abstract/document/715935" current
• 10:5410:54, 15 February 2023 diff hist +326‎ N Chu-Liu-Edmonds Algorithm (Directed (Optimum Branchings), General MST Minimum Spanning Tree (MST)) ‎ Created page with "== Time Complexity == $O(EV)$ == Space Complexity == $O(E+V)$ words ((derived in sheet)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1965 == Reference == https://nvlpubs.nist.gov/nistpubs/jres/71b/jresv71bn4p233_a1b.pdf" current
• 10:5410:54, 15 February 2023 diff hist +360‎ N Tarjan (directed, general) (Directed (Optimum Branchings), General MST Minimum Spanning Tree (MST)) ‎ Created page with "== Time Complexity == $O(ElogV)$ == Space Complexity == $O(E)$ words (https://onlinelibrary.wiley.com/doi/10.1002/net.3230070103) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://onlinelibrary.wiley.com/doi/10.1002/net.3230070103" current
• 10:5410:54, 15 February 2023 diff hist +309‎ N Pettie, Ramachandran (Undirected, General MST Minimum Spanning Tree (MST)) ‎ Created page with "== Time Complexity == unknown but optimal == Space Complexity == $O(E)$ auxiliary? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 2002 == Reference == https://dl.acm.org/doi/10.1145/505241.505243" current
• 10:5410:54, 15 February 2023 diff hist +323‎ N Fredman & Willard (Undirected, Integer Weights MST Minimum Spanning Tree (MST)) ‎ Created page with "== Time Complexity == $O(E+V)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Trans-dichotomous == Year == 1991 == Reference == https://www.sciencedirect.com/science/article/pii/S0022000005800649?via%3Dihub" current
• 10:5410:54, 15 February 2023 diff hist +317‎ N Cheriton-Tarjan (planar) (Undirected, Planar MST Minimum Spanning Tree (MST)) ‎ Created page with "== Time Complexity == $O(V)$ == Space Complexity == $O(V)$ auxiliary words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://epubs.siam.org/doi/abs/10.1137/0205051" current
• 10:5410:54, 15 February 2023 diff hist +319‎ N Gabow et al, Section 2 (Undirected, General MST Minimum Spanning Tree (MST)) ‎ Created page with "== Time Complexity == $O(E*log(beta(E, V)$)) == Space Complexity == $O(E)$ auxiliary? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1986 == Reference == https://link.springer.com/article/10.1007/BF02579168" current
• 10:5410:54, 15 February 2023 diff hist +318‎ N Cheriton-Tarjan (dense) (Undirected, Dense MST Minimum Spanning Tree (MST)) ‎ Created page with "== Time Complexity == $O(E)$ == Space Complexity == $O(E)$ auxiliary? words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://epubs.siam.org/doi/abs/10.1137/0205051" current
• 10:5410:54, 15 February 2023 diff hist +409‎ N Fredman & Tarjan (Undirected, General MST Minimum Spanning Tree (MST)) ‎ Created page with "== Time Complexity == $O(E*beta(E, V)$) where beta(m, n) = min(i such that log^(i)(n)≤m/n); this is also $O(E (log-star)$V) == Space Complexity == $O(E)$ auxiliary? words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://dl.acm.org/citation.cfm?id=28874" current
• 10:5410:54, 15 February 2023 diff hist +270‎ N Prim's algorithm + binary heap (Undirected, General MST Minimum Spanning Tree (MST)) ‎ Created page with "== Time Complexity == $O(ElogV)$ == Space Complexity == $O(V)$ auxiliary? words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference ==" current
• 10:5410:54, 15 February 2023 diff hist +308‎ N Multistep (SCCs Strongly Connected Components) ‎ Created page with "== Time Complexity == $O(V^{2}+E)$ == Space Complexity == $O(V+E)$ total? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2014 == Reference == https://ieeexplore.ieee.org/abstract/document/6877288" current
• 10:5410:54, 15 February 2023 diff hist +410‎ N Geldenhuys-Valmari (SCCs Strongly Connected Components) ‎ Created page with "== Time Complexity == $O(V+E)$ == Space Complexity == $O(V)$? words ((follow-up from Tarjan's algorithm)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://www.semanticscholar.org/paper/Depth-First-Search-and-Linear-Graph-Algorithms-Tarjan/385742fffcf113656f0d3cf6c06ef95cb8439dc6" current
• 10:5410:54, 15 February 2023 diff hist +221‎ N (many more...) (2-dimensional Convex Hull, Dynamic Convex Hull) ‎ Created page with "== Time Complexity == == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == == Reference ==" current
• 10:5410:54, 15 February 2023 diff hist +359‎ N Dynamic 2-d Convex Hull, Overmars and van Leeuwen (2-dimensional Convex Hull, Dynamic Convex Hull) ‎ Created page with "== Time Complexity == $O(log^{2}(n)$) per operation, $O(n*log^{2}(n)$) total == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1980 == Reference == https://www.sciencedirect.com/science/article/pii/002200008190012X?via%3Dihub" current
• 10:5410:54, 15 February 2023 diff hist +340‎ N Online 2-d Convex Hull, Preparata (2-dimensional Convex Hull, Online Convex Hull) ‎ Created page with "== Time Complexity == $O(logn)$ per operation, $O(n*log(n)$) total == Space Complexity == $O(n)$ words (easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1979 == Reference == https://dl.acm.org/doi/abs/10.1145/359131.359132" current
• 10:5410:54, 15 February 2023 diff hist +353‎ N N-dimensional Quickhull (d-dimensional Convex Hull Convex Hull) ‎ Created page with "== Time Complexity == $O(n*f(h)$/h) where f(h) denotes the maximum number of facets with h vertices == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1996 == Reference == https://dl.acm.org/doi/pdf/10.1145/235815.235821" current
• 10:5410:54, 15 February 2023 diff hist +286‎ N Chand-Kapur, Gift Wrapping (d-dimensional Convex Hull Convex Hull) ‎ Created page with "== Time Complexity == $O(n*f_1)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1970 == Reference == https://dl.acm.org/doi/pdf/10.1145/321556.321564" current
• 10:5410:54, 15 February 2023 diff hist +295‎ N Seidel's Shelling Algorithm (d-dimensional Convex Hull Convex Hull) ‎ Created page with "== Time Complexity == $O(n^{2}+f_1*log(n)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1986 == Reference == https://dl.acm.org/doi/pdf/10.1145/12130.12172" current
• 10:5410:54, 15 February 2023 diff hist +388‎ N NIEVERGELT. J.. AND PREPARATA (Section 2) (Reporting all intersection points / general polygons Line segment intersection) ‎ Created page with "== Time Complexity == $O((n+k)$log n) == Space Complexity == $O(n+k)$ words (https://courses.cs.duke.edu/cps234/spring04/papers/NP82.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1982 == Reference == https://pdfs.semanticscholar.org/a571/cc92218132a1b0e65c2adbf663c79d015737.pdf" current
• 10:5410:54, 15 February 2023 diff hist +462‎ N Jiang, Song, Weinstein and Zhang ( Linear Programming) ‎ Created page with "== Time Complexity == $O(n^(max(omega, {2.5}-alpha/{2}, {37}/{18}))*polylog(n, m, L))$, where omega is the exponent on matrix multiplication, alpha is the dual exponent of matrix multiplication; currently $O(n^{2.37285956})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2020 == Reference == https://arxiv.org/abs/1810.07896" current
• 10:5410:54, 15 February 2023 diff hist +380‎ N CHAZELLE 1986 (Counting number of intersection points / line segments Line segment intersection) ‎ Created page with "== Time Complexity == $O(n^{1.695})$ == Space Complexity == $O(n)$ words (https://www.sciencedirect.com/science/article/pii/0022000086900255) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1986 == Reference == https://www.sciencedirect.com/science/article/pii/0022000086900255" current
• 10:5410:54, 15 February 2023 diff hist +452‎ N Parameter-expanded expectation maximization (PX-EM) (Maximum Likelihood Methods in Unknown Latent Variables Maximum Likelihood Methods in Unknown Latent Variables) ‎ Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta (+ alpha) and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1998 == Reference == http://www.stat.ucla.edu/~ywu/research/papers/PXEM.pdf" current
• 10:5410:54, 15 February 2023 diff hist +368‎ N Vaidya ( Linear Programming) ‎ Created page with "== Time Complexity == $O(((m+n)$n^{2}+(m+n)^{1.5}*n)L^{2} logL loglogL) == Space Complexity == $O((nm+n^{2})$L)? words (can be easily derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://link.springer.com/article/10.1007/BF01580859"
• 10:5410:54, 15 February 2023 diff hist +473‎ N Peng, Vempala (Sparse Linear system of equations) ‎ Created page with "== Time Complexity == $O(max(m^{(omega-{2})/(omega-{1})}*n^{2}, n^{({5}*omega-{4})/(omega+{1})})*log^{2}(k/epsilon))$ where omega is the exponent on the complexity of matrix multiplication; currently $O(n^{2.331642})$ == Space Complexity == words () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2020 == Reference == https://arxiv.org/abs/2007.10254" current