User contributions for Admin

10:5410:54, 15 February 2023 diff hist +306‎ N 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" current
10:5410:54, 15 February 2023 diff hist +261‎ N 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 ==" current
10:5410:54, 15 February 2023 diff hist +402‎ N 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" current
10:5410:54, 15 February 2023 diff hist 0‎ Fomin; Gaspers & Saurabh ( ‎No edit summary Tag: Reverted
10:5410:54, 15 February 2023 diff hist +253‎ N 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 ==" current
10:5410:54, 15 February 2023 diff hist +304‎ N 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:5410:54, 15 February 2023 diff hist +335‎ N 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" current
10:5410:54, 15 February 2023 diff hist +304‎ N 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" current
10:5410:54, 15 February 2023 diff hist +306‎ N 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" current
10:5410:54, 15 February 2023 diff hist +267‎ N 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 ==" current
10:5410:54, 15 February 2023 diff hist +375‎ N 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" current
10:5410:54, 15 February 2023 diff hist +384‎ N 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" current
10:5410:54, 15 February 2023 diff hist +407‎ N 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" current
10:5410:54, 15 February 2023 diff hist +417‎ N 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" current
10:5410:54, 15 February 2023 diff hist +362‎ N 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" current
10:5410:54, 15 February 2023 diff hist +379‎ N 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" current
10:5410:54, 15 February 2023 diff hist +341‎ N 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" current
10:5410:54, 15 February 2023 diff hist +375‎ N 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" current
10:5410:54, 15 February 2023 diff hist +384‎ N 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" current
10:5410:54, 15 February 2023 diff hist +402‎ N 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" current
10:5410:54, 15 February 2023 diff hist +325‎ N 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" current
10:5410:54, 15 February 2023 diff hist +342‎ N 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" current
10:5410:54, 15 February 2023 diff hist +375‎ N 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" current
10:5410:54, 15 February 2023 diff hist +384‎ N 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" current
10:5410:54, 15 February 2023 diff hist +325‎ N 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" current
10:5410:54, 15 February 2023 diff hist +363‎ N 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" current
10:5410:54, 15 February 2023 diff hist +381‎ N 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=" current
10:5410:54, 15 February 2023 diff hist +1‎ Goldberg & Rao (Parallel) (Integer Maximum Flow Maximum Flow) ‎No edit summary Tag: Reverted
10:5410:54, 15 February 2023 diff hist +343‎ N 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:5410:54, 15 February 2023 diff hist +310‎ N 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" current
10:5410:54, 15 February 2023 diff hist +328‎ N 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" current
10:5410:54, 15 February 2023 diff hist +314‎ N 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" current
10:5410:54, 15 February 2023 diff hist −30‎ Kathuria, Liu, Sidford ( Maximum Flow) ‎No edit summary
10:5410:54, 15 February 2023 diff hist +382‎ N 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:5410:54, 15 February 2023 diff hist +364‎ N 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" current
10:5410:54, 15 February 2023 diff hist +362‎ N 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" current
10:5410:54, 15 February 2023 diff hist +327‎ N 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" current
10:5410:54, 15 February 2023 diff hist +389‎ N 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" current
10:5410:54, 15 February 2023 diff hist +365‎ N 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" current
10:5410:54, 15 February 2023 diff hist +333‎ N 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" current
10:5410:54, 15 February 2023 diff hist +284‎ N 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" current
10:5410:54, 15 February 2023 diff hist +284‎ N 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" current
10:5410:54, 15 February 2023 diff hist +288‎ N ( 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" current
10:5410:54, 15 February 2023 diff hist +319‎ N 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" current
10:5410:54, 15 February 2023 diff hist +322‎ N 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" current
10:5410:54, 15 February 2023 diff hist +328‎ N 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" current
10:5410:54, 15 February 2023 diff hist +363‎ N 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" current
10:5410:54, 15 February 2023 diff hist +350‎ N 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:5410:54, 15 February 2023 diff hist +9‎ Bansal, Williams (Boolean Matrix Multiplication (Combinatorial) Matrix Product) ‎No edit summary Tag: Reverted
10:5410:54, 15 February 2023 diff hist +346‎ N 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"

User contributions for Admin

15 February 2023

Navigation menu

Search