New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 10:54, 15 February 2023 Jiang, Song, Weinstein and Zhang ( Linear Programming) (hist | edit) [462 bytes] Admin (talk | contribs) (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")
- 10:54, 15 February 2023 CHAZELLE 1986 (Counting number of intersection points / line segments Line segment intersection) (hist | edit) [380 bytes] Admin (talk | contribs) (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")
- 10:54, 15 February 2023 Parameter-expanded expectation maximization (PX-EM) (Maximum Likelihood Methods in Unknown Latent Variables Maximum Likelihood Methods in Unknown Latent Variables) (hist | edit) [452 bytes] Admin (talk | contribs) (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")
- 10:54, 15 February 2023 Vaidya ( Linear Programming) (hist | edit) [346 bytes] Admin (talk | contribs) (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:54, 15 February 2023 Peng, Vempala (Sparse Linear system of equations) (hist | edit) [473 bytes] Admin (talk | contribs) (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")
- 10:54, 15 February 2023 Asymptotically fast Toeplitz algorithms (Toeplitz Linear system of equations) (hist | edit) [319 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log^{2}(n)$) == Space Complexity == $O(n*log^{2}(n)$)? words (upper bound) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2008? == Reference == https://epubs.siam.org/doi/10.1137/040617200")
- 10:54, 15 February 2023 Matrix inverse (General Linear system of equations) (hist | edit) [384 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^omega)$ where omega is the exponent on the complexity of matrix multiplication;<br/>currently $O(n^{2.37285956})$ == Space Complexity == $O(n^{2})$ words (equivalent to matrix multiplication) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == == Reference ==")
- 10:54, 15 February 2023 Koivisto ( Chromatic Polynomial) (hist | edit) [306 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031393")
- 10:54, 15 February 2023 LU decomposition (General Linear system of equations) (hist | edit) [261 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == O (n^{3}) == Space Complexity == $O(n^{2})$ words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == == Reference ==")
- 10:54, 15 February 2023 Bjorklund, Husfeldt, Proposition 3 ( Chromatic Polynomial) (hist | edit) [402 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n)$) == Space Complexity == $O({2}^n*poly(n)$) => $O({1.292}^n)$ words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392")
- 10:54, 15 February 2023 Zykov (deletion-contraction) ( Chromatic Polynomial) (hist | edit) [253 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((({1}+sqrt5)$/{2})^(n+m)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1949 == Reference ==")
- 10:54, 15 February 2023 Fomin; Gaspers & Saurabh ( (hist | edit) [304 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.6262}^n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2007 == Reference == https://link.springer.com/chapter/10.1007/978-3-540-73545-8_9")
- 10:54, 15 February 2023 Fürer, Kasiviswanathan ( (hist | edit) [335 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.7702}^n*poly(n)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2005 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.634.4498&rep=rep1&type=pdf")
- 10:54, 15 February 2023 Angelsmark, Jonsson ( (hist | edit) [304 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.7879}^n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://link.springer.com/chapter/10.1007/978-3-540-45193-8_6")
- 10:54, 15 February 2023 Koivisto ( Chromatic Number) (hist | edit) [306 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031393")
- 10:54, 15 February 2023 BFS/DFS for connected components ( (hist | edit) [267 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m)$ == Space Complexity == $O(n)$ auxiliary words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference ==")
- 10:54, 15 February 2023 Bjorklund, Husfeldt, Proposition 2 ( Chromatic Number) (hist | edit) [375 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2.2461}^n)$ == Space Complexity == $O(poly(n)$) words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392")
- 10:54, 15 February 2023 Bjorklund, Husfeldt, Theorem 1 ( Chromatic Number) (hist | edit) [384 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n)$) == Space Complexity == $O({2}^n*poly(n)$) words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392")
- 10:54, 15 February 2023 Byskov ( Chromatic Number) (hist | edit) [407 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({80}^(n/{5})$) ~ $O({2.4023}^n)$ == Space Complexity == $O({2}^n)$ words (https://www.sciencedirect.com/science/article/pii/S0167637704000409) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://www.sciencedirect.com/science/article/pii/S0167637704000409")
- 10:54, 15 February 2023 Lawler ( Chromatic Number) (hist | edit) [417 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn({1}+{3}^({1}/{3})$)^n) == Space Complexity == $O({2}^n*log(n)$) words (https://www.sciencedirect.com/science/article/pii/S0167637704000409) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://www.sciencedirect.com/science/article/pii/002001907690065X?via%3Dihub")
- 10:54, 15 February 2023 Eppstein ( Chromatic Number) (hist | edit) [362 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(({4}/{3}+{3}^({4}/{3})$/{4})^n) ~ $O({2.4151}^n)$ == Space Complexity == $O({2}^n)$ words (https://arxiv.org/pdf/cs/0011009.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://arxiv.org/pdf/cs/0011009.pdf")
- 10:54, 15 February 2023 Christofides ( Chromatic Number) (hist | edit) [379 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n!*poly(n)$) == Space Complexity == $O(poly(n)$) words (https://link.springer.com/article/10.1007/s00453-007-9149-8) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://academic.oup.com/comjnl/article/14/1/38/356253?login=true")
- 10:54, 15 February 2023 Zamir ( 6 - Graph Coloring) (hist | edit) [341 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(({2}-eps)$^n) for some eps>{0} == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2021 == Reference == https://drops.dagstuhl.de/opus/volltexte/2021/14182/pdf/LIPIcs-ICALP-2021-113.pdf")
- 10:54, 15 February 2023 Bjorklund, Husfeldt, Proposition 2 ( 6 - Graph Coloring) (hist | edit) [375 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2.2461}^n)$ == Space Complexity == $O(poly(n)$) words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392")
- 10:54, 15 February 2023 Bjorklund, Husfeldt, Theorem 1 ( 6 - Graph Coloring) (hist | edit) [384 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n)$) == Space Complexity == $O({2}^n*poly(n)$) words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392")
- 10:54, 15 February 2023 Byskov, Theorem 20 ( 6 - Graph Coloring) (hist | edit) [402 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2.2680}^n)$ == Space Complexity == $O({2}^n)$ words (https://www.sciencedirect.com/science/article/pii/S0167637704000409) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0167637704000409?via%3Dihub")
- 10:54, 15 February 2023 Byskov, Theorem 14 ( 6 - Graph Coloring) (hist | edit) [325 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2.3289}^n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0167637704000409?via%3Dihub")
- 10:54, 15 February 2023 Zamir ( 5 - Graph Coloring) (hist | edit) [342 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(({2}-eps)$^n) for some eps>{0} == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2021 == Reference == https://drops.dagstuhl.de/opus/volltexte/2021/14182/pdf/LIPIcs-ICALP-2021-113.pdf")
- 10:54, 15 February 2023 Bjorklund, Husfeldt, Proposition 2 ( 5 - Graph Coloring) (hist | edit) [375 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2.2461}^n)$ == Space Complexity == $O(poly(n)$) words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392")
- 10:54, 15 February 2023 Bjorklund, Husfeldt, Theorem 1 ( 5 - Graph Coloring) (hist | edit) [384 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n)$) == Space Complexity == $O({2}^n*poly(n)$) words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392")
- 10:54, 15 February 2023 Byskov ( 5 - Graph Coloring) (hist | edit) [325 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2.1592}^n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0167637704000409?via%3Dihub")
- 10:54, 15 February 2023 Alman, Vassilevska Williams ( Matrix Multiplication) (hist | edit) [363 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2.37285956})$ == Space Complexity == $O(n^{2})$ words (through re-use of space in recursive branches (response from Virginia)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2020 == Reference == https://arxiv.org/pdf/2010.05846.pdf")
- 10:54, 15 February 2023 Method of Four Russians ( Matrix Multiplication) (hist | edit) [381 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3}/log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference == https://scholar.google.com/scholar?hl=en&as_sdt=0%2C22&q=On+economical+construction+of+the+transitive+closure+of+an+oriented+graph.&btnG=")
- 10:54, 15 February 2023 Goldberg & Rao (Parallel) (Integer Maximum Flow Maximum Flow) (hist | edit) [344 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{1.66} log(V)$ log(U)) == Space Complexity == $O(V^{2})$ words (https://dl.acm.org/citation.cfm?id=290181) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == PRAM == Year == 1997 == Reference == https://dl.acm.org/citation.cfm?id=290181")
- 10:54, 15 February 2023 Chen et al ( Maximum Flow) (hist | edit) [310 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E^({1}+o({1})$)*log(U)) == Space Complexity == $O(E)$ words ((derived in notes)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2022 == Reference == https://arxiv.org/abs/2203.00671")
- 10:54, 15 February 2023 Gao, Liu, Peng ( Maximum Flow) (hist | edit) [328 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E^({3}/{2}-{1}/{328})$*log(U)*polylog(E)) == Space Complexity == $O(E)$ words ((derived in notes)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2021 == Reference == https://arxiv.org/abs/2101.07233")
- 10:54, 15 February 2023 Brand et al ( Maximum Flow) (hist | edit) [314 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((E+V^{1.5})$log(U)polylog(V, E, log U)) == Space Complexity == $O(E)$ words ((derived in notes)) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2021 == Reference == https://arxiv.org/abs/2101.05719")
- 10:54, 15 February 2023 Kathuria, Liu, Sidford ( Maximum Flow) (hist | edit) [352 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E^({1}+o({1})$)/sqrt(eps)) == Space Complexity == $O(E)$ or $O(V^{2})$ ? words (unsure, please look) == Description == == Approximate? == Approximate Approximation Factor: 1+eps == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2020 == Reference == https://epubs.siam.org/doi/abs/10.1137/20M1383525")
- 10:54, 15 February 2023 Madry ( Maximum Flow) (hist | edit) [364 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E^({10}/{7})$U^({1}/{7})polylog(V, E, log U)) == Space Complexity == $O(E)$ words ((derived in notes)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2016 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7782974")
- 10:54, 15 February 2023 Lee, Sidford ( Maximum Flow) (hist | edit) [362 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E*sqrt(V)$*log^{2}(U)*polylog(E, V, log(U)) == Space Complexity == $O(E)$ words ((derived in notes)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2014 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6979027")
- 10:54, 15 February 2023 Gabow ( Maximum Flow) (hist | edit) [327 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE*logU)$ == Space Complexity == $O(E)$ words (can be derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == https://www.sciencedirect.com/science/article/pii/002200008590039X")
- 10:54, 15 February 2023 Shiloach ( Maximum Flow) (hist | edit) [389 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{3}*log(V)$/p) == Space Complexity == $O(E)$ words (can be derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Parallel RAM (unclear what type; seems like any could work?) == Year == 1981 == Reference == http://users.umiacs.umd.edu/~vishkin/TEACHING/4CLASS/SV82-maxflow.pdf")
- 10:54, 15 February 2023 Galil ( Maximum Flow) (hist | edit) [365 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^({5}/{3})$E^({2}/{3})) == Space Complexity == $O(E)$ words (https://link.springer.com/article/10.1007/BF00264254) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1978 == Reference == https://link.springer.com/article/10.1007/BF00264254")
- 10:54, 15 February 2023 MKM Algorithm ( Maximum Flow) (hist | edit) [333 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{3})$ == Space Complexity == $O(E)$ words (https://core.ac.uk/download/pdf/81946904.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1978 == Reference == https://eprints.utas.edu.au/160/1/iplFlow.pdf")
- 10:54, 15 February 2023 Parallel Merge Sort - Cole (2) ( Sorting - Comparison) (hist | edit) [284 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW PRAM == Year == 1988 == Reference == https://epubs.siam.org/doi/abs/10.1137/0217049")
- 10:54, 15 February 2023 Parallel Merge Sort - Cole (1) ( Sorting - Comparison) (hist | edit) [284 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1988 == Reference == https://epubs.siam.org/doi/abs/10.1137/0217049")
- 10:54, 15 February 2023 ( Negative Triangle) (hist | edit) [288 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 2018 == Reference == https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 1.5")
- 10:54, 15 February 2023 Larsen, Williams (follows from Theorem 2.1) ( Online Matrix Vector Multiplication (OMV)) (hist | edit) [319 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^({11}/{4})$ / sqrt(log n)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Cell Probe == Year == 2017 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611974782.142")
- 10:54, 15 February 2023 Larsen, Williams (Theorem 1.1) ( Online Matrix Vector Multiplication (OMV)) (hist | edit) [322 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} / {2}^(Omega(sqrt(log n)$))) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2017 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611974782.142")
- 10:54, 15 February 2023 Williams ( Online Matrix Vector Multiplication (OMV)) (hist | edit) [328 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} / (log n)$^{2}) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2007 == Reference == http://www.cs.cmu.edu/~./theorylunch/pastSemesterIndices/slides/20070117.pdf")