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).

Logs
(newest | oldest) View ( | ) (20 | 50 | 100 | 250 | 500)
  • 10:54, 15 February 2023 Admin talk contribs created page 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")
  • 10:54, 15 February 2023 Admin talk contribs created page Matrix inverse (General Linear system of equations) (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 Admin talk contribs created page Asymptotically fast Toeplitz algorithms (Toeplitz Linear system of equations) (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 Admin talk contribs created page Koivisto ( Chromatic Polynomial) (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 Admin talk contribs created page LU decomposition (General Linear system of equations) (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 Admin talk contribs created page Bjorklund, Husfeldt, Proposition 3 ( Chromatic Polynomial) (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 Admin talk contribs created page Zykov (deletion-contraction) ( Chromatic Polynomial) (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 Admin talk contribs created page Fomin; Gaspers & Saurabh ( (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 Admin talk contribs created page Fürer, Kasiviswanathan ( (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 Admin talk contribs created page Angelsmark, Jonsson ( (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 Admin talk contribs created page BFS/DFS for connected components ( (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 Admin talk contribs created page Koivisto ( Chromatic Number) (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 Admin talk contribs created page Bjorklund, Husfeldt, Proposition 2 ( Chromatic Number) (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 Admin talk contribs created page Bjorklund, Husfeldt, Theorem 1 ( Chromatic Number) (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 Admin talk contribs created page Byskov ( Chromatic Number) (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 Admin talk contribs created page Lawler ( Chromatic Number) (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 Admin talk contribs created page Eppstein ( Chromatic Number) (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 Admin talk contribs created page Christofides ( Chromatic Number) (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 Admin talk contribs created page Zamir ( 6 - Graph Coloring) (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 Admin talk contribs created page Bjorklund, Husfeldt, Proposition 2 ( 6 - Graph Coloring) (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 Admin talk contribs created page Bjorklund, Husfeldt, Theorem 1 ( 6 - Graph Coloring) (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 Admin talk contribs created page Byskov, Theorem 20 ( 6 - Graph Coloring) (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 Admin talk contribs created page Byskov, Theorem 14 ( 6 - Graph Coloring) (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 Admin talk contribs created page Zamir ( 5 - Graph Coloring) (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 Admin talk contribs created page Bjorklund, Husfeldt, Proposition 2 ( 5 - Graph Coloring) (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 Admin talk contribs created page Bjorklund, Husfeldt, Theorem 1 ( 5 - Graph Coloring) (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 Admin talk contribs created page Byskov ( 5 - Graph Coloring) (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 Admin talk contribs created page Alman, Vassilevska Williams ( Matrix Multiplication) (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 Admin talk contribs created page Method of Four Russians ( Matrix Multiplication) (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 Admin talk contribs created page Goldberg & Rao (Parallel) (Integer Maximum Flow Maximum Flow) (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 Admin talk contribs created page Chen et al ( Maximum Flow) (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 Admin talk contribs created page Gao, Liu, Peng ( Maximum Flow) (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 Admin talk contribs created page Brand et al ( Maximum Flow) (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 Admin talk contribs created page Kathuria, Liu, Sidford ( Maximum Flow) (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 Admin talk contribs created page Madry ( Maximum Flow) (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 Admin talk contribs created page Lee, Sidford ( Maximum Flow) (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 Admin talk contribs created page Gabow ( Maximum Flow) (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 Admin talk contribs created page Shiloach ( Maximum Flow) (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 Admin talk contribs created page Galil ( Maximum Flow) (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 Admin talk contribs created page MKM Algorithm ( Maximum Flow) (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 Admin talk contribs created page Parallel Merge Sort - Cole (2) ( Sorting - Comparison) (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 Admin talk contribs created page Parallel Merge Sort - Cole (1) ( Sorting - Comparison) (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 Admin talk contribs created page ( Negative Triangle) (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 Admin talk contribs created page Larsen, Williams (follows from Theorem 2.1) ( Online Matrix Vector Multiplication (OMV)) (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 Admin talk contribs created page Larsen, Williams (Theorem 1.1) ( Online Matrix Vector Multiplication (OMV)) (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 Admin talk contribs created page Williams ( Online Matrix Vector Multiplication (OMV)) (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")
  • 10:54, 15 February 2023 Admin talk contribs created page Yu (Boolean Matrix Multiplication (Combinatorial) Matrix Product) (Created page with "== Time Complexity == $O(n^{3}*poly(log log n)$/log^{4} n) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM with word size w = Omega(log n) == Year == 2015 == Reference == https://www.sciencedirect.com/science/article/pii/S0890540118300099")
  • 10:54, 15 February 2023 Admin talk contribs created page Chan (Boolean Matrix Multiplication (Combinatorial) Matrix Product) (Created page with "== Time Complexity == $O(n^{3} * (log log n)$^{3} / log^{3} n) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM with word size w = log n == Year == 2015 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611973730.16")
  • 10:54, 15 February 2023 Admin talk contribs created page Bansal, Williams (Boolean Matrix Multiplication (Combinatorial) Matrix Product) (Created page with "== Time Complexity == $O(n^{3} * (log log n)$^{2} / log^{2.25} n) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Word RAM with word size w = log n == Year == 2009 == Reference == https://ieeexplore.ieee.org/abstract/document/5438580")
  • 10:54, 15 February 2023 Admin talk contribs created page Method of Four Russians (Boolean Matrix Multiplication (Combinatorial) Matrix Product) (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 == 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=")
(newest | oldest) View ( | ) (20 | 50 | 100 | 250 | 500)
Retrieved from "https://algorithm-wiki.csail.mit.edu/wiki/Special:Log/Admin"