×

Downey, Rodney Graham

Compute Distance To:
Author ID: downey.rodney-graham Recent zbMATH articles by "Downey, Rodney Graham"
Published as: Downey, Rod; Downey, Rodney G.; Downey, R. G.; Downey, Rod G.; Downey, Rodney; Downey, R.; Downey, Rodney Graham
Homepage: http://homepages.mcs.vuw.ac.nz/~downey/
External Links: MGP · Wikidata · ResearchGate · dblp · GND · IdRef
Documents Indexed: 279 Publications since 1983, including 5 Books
18 Contributions as Editor · 2 Further Contributions
Reviewing Activity: 118 Reviews
Biographic References: 9 Publications
Co-Authors: 146 Co-Authors with 239 Joint Publications
2,797 Co-Co-Authors
all top 5

Co-Authors

57 single-authored
35 Fellows, Michael Ralph
24 Greenberg, Noam
20 Lempp, Steffen
19 Hirschfeldt, Denis Roman
18 Ng, KengMeng
16 Melnikov, Alexander G.
15 Cholak, Peter A.
13 Nies, André Otfrid
12 Jockusch, Carl G. jun.
9 Miller, Joseph S.
9 Shore, Richard Arnold
8 Remmel, Jeffrey B.
7 Barmpalias, George
7 Wu, Guohua
6 Kach, Asher M.
6 Stob, Michael
6 Turetsky, Daniel D.
5 Bienvenu, Laurent
5 McCartin, Catherine
5 Montalbán, Antonio
5 Yu, Liang
4 Bodlaender, Hans L.
4 Cai, Liming
4 Chen, Jian-er
4 Coles, Richard J.
4 Griffiths, Evan J.
4 Knight, Julia F.
4 LaForte, Geoffrey L.
4 Merkle, Wolfgang
4 Solomon, Reed
3 Chong, Chi Tat
3 Goncharov, Sergeĭ Savost’yanovich
3 Harrington, Leo A.
3 Harrison-Trainor, Matthew
3 Khoussainov, Bakhadyr M.
3 LaForte, Geoff
3 Moses, Michael F.
3 Rosamond, Frances A.
3 Slaman, Theodore A.
3 Turetsky, Dan
3 Weber, Rebecca
2 Abrahamson, Karl A.
2 Ambos-Spies, Klaus
2 Brattka, Vasco
2 Brendle, Jörg
2 Cenzer, Douglas
2 Csima, Barbara F.
2 Ding, Decheng
2 Fortnow, Lance J.
2 Goldblatt, Robert Ian
2 Hermelin, Danny
2 Herrmann, Eberhard
2 Kalimullin, Iskander Shagitovich
2 McInerney, Michael
2 Mileti, Joseph R.
2 Nandakumar, Satyadev
2 Regan, Kenneth W.
2 Reimann, Jan
2 Schupp, Paul E.
2 Stege, Ulrike
2 Stephan, Frank
2 Terwijn, Sebastiaan A.
2 Welch, Lawrence V.
2 Yang, Yue
1 Arai, Toshiyasu
1 Arthur, Katherine
1 Ash, Christopher John
1 Bailey, Colin G.
1 Baker, Ruth Elizabeth
1 Barrett, Jordan Mitchell
1 Batey, Mavis
1 Bazhenov, Nikolaĭ Alekseevich
1 Berrick, A. Jon
1 Blaylock, Rich
1 Boden, Margaret A.
1 Bowen, Jonathan P.
1 Brodhead, Paul
1 Burton, Benjamin A.
1 Cai, Mingzhong
1 Campbell-Kelly, Martin
1 Carpenter, Brian E.
1 Cattell, Kevin
1 Caughey, Catherine
1 Chih, Ellen S.
1 Conder, Marston D. E.
1 Copeland, B. Jack
1 Courcelle, Bruno
1 Day, Adam R.
1 Dehne, Frank
1 Diamondstone, David E.
1 Dinneen, Michael J.
1 Doran, Robert W.
1 Egan, Judith
1 Epstein, Rachel
1 Estivill-Castro, Vladimir
1 Feng, Qi
1 Flum, Jörg
1 Fomin, Fedor V.
1 Furedi, Zoltan
1 Gale, Amy
...and 78 more Co-Authors
all top 5

Serials

41 Annals of Pure and Applied Logic
30 The Journal of Symbolic Logic
13 Theoretical Computer Science
10 Journal of Computer and System Sciences
10 Proceedings of the American Mathematical Society
10 Transactions of the American Mathematical Society
9 Zeitschrift für Mathematische Logik und Grundlagen der Mathematik
7 Notre Dame Journal of Formal Logic
7 Mathematical Logic Quarterly (MLQ)
7 Journal of Mathematical Logic
6 Archive for Mathematical Logic
5 Israel Journal of Mathematics
5 Journal of Algebra
5 Journal of the London Mathematical Society. Second Series
5 The Bulletin of Symbolic Logic
4 Advances in Mathematics
4 Theory of Computing Systems
3 SIAM Journal on Computing
3 New Zealand Journal of Mathematics
3 Computability
2 Bulletin of the Australian Mathematical Society
2 Information Processing Letters
2 Mathematical Proceedings of the Cambridge Philosophical Society
2 Algebra i Logika
2 Illinois Journal of Mathematics
2 Rendiconti del Seminario Matematico
2 Oberwolfach Reports
2 Lecture Notes in Computer Science
2 Logical Methods in Computer Science
1 Archiv für Mathematische Logik und Grundlagenforschung
1 Discrete Applied Mathematics
1 Algebra and Logic
1 Bulletin of the London Mathematical Society
1 Fundamenta Mathematicae
1 Journal of Combinatorial Theory. Series A
1 Memoirs of the American Mathematical Society
1 Pacific Journal of Mathematics
1 Combinatorica
1 Order
1 Algorithmica
1 Information and Computation
1 Journal of the American Mathematical Society
1 International Journal of Algebra and Computation
1 MSCS. Mathematical Structures in Computer Science
1 Journal of the Australian Mathematical Society. Series A
1 Notices of the American Mathematical Society
1 Chicago Journal of Theoretical Computer Science
1 Bulletin of the European Association for Theoretical Computer Science EATCS
1 Tsinghua Science and Technology
1 Journal of Universal Computer Science
1 Annals of Mathematics Studies
1 Lecture Notes in Logic
1 De Gruyter Series in Logic and Its Applications
1 Mathematical Medley
1 Computer Science Review
1 Proceedings of the American Mathematical Society. Series B
1 Texts in Computer Science
1 Theory and Applications of Computability

Publications by Year

Citations contained in zbMATH Open

242 Publications have been cited 3,826 times in 2,254 Documents Cited by Year
Parameterized complexity. Zbl 0914.68076
Downey, R. G.; Fellows, M. R.
481
1998
Fundamentals of parameterized complexity. Zbl 1358.68006
Downey, Rodney G.; Fellows, Michael R.
425
2013
Algorithmic randomness and complexity. Zbl 1221.68005
Downey, Rodney G.; Hirschfeldt, Denis R.
349
2010
On problems without polynomial kernels. Zbl 1192.68288
Bodlaender, Hans L.; Downey, Rodney G.; Fellows, Michael R.; Hermelin, Danny
179
2009
Fixed-parameter tractability and completeness II: On completeness for W[1]. Zbl 0873.68059
Downey, Rod G.; Fellows, Michael R.
130
1995
Parameterized complexity after (almost) ten years: Review and open questions. Zbl 0961.68533
Downey, Rodney G.; Fellows, Michael R.
108
1999
Fixed-parameter tractability and completeness. I: Basic results. Zbl 0830.68063
Downey, Rod G.; Fellows, Michael R.
107
1995
Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues. Zbl 0828.68077
Abrahamson, Karl A.; Downey, Rodney G.; Fellows, Michael R.
53
1995
Parametrized complexity: A framework for systematically confronting computational intractability. Zbl 0935.68046
Downey, Rodney G.; Fellows, Michael R.; Stege, Ulrike
52
1999
Fixed-parameter tractability and completeness. Zbl 0768.68136
Downey, Rod G.; Fellows, Michael R.
50
1992
Parameterized computational feasibility. Zbl 0834.68046
Downey, Rodney G.; Fellows, Michael R.
43
1995
Calibrating randomness. Zbl 1113.03037
Downey, Rod; Hirschfeldt, Dennis R.; Nies, André; Terwijn, Sebastiaan A.
42
2006
Computability theory and linear orderings. Zbl 0941.03045
Downey, R. G.
38
1998
D-r.e. degrees and the nondiamond theorem. Zbl 0628.03030
Downey, Rod
33
1989
Fixed-parameter tractability and completeness. III: Some structural aspects of the \(W\) hierarchy. Zbl 0799.68087
Downey, Rod; Fellows, Michael
32
1993
Trivial reals. Zbl 1044.03027
Downey, Rod G.; Hirschfeldt, Denis R.; Nies, André; Stephan, Frank
31
2003
The isomorphism problem for torsion-free abelian groups is analytic complete. Zbl 1156.03042
Downey, Rod; Montalbán, Antonio
31
2008
The parametrized complexity of some fundamental problems in coding theory. Zbl 0943.68079
Downey, Rod G.; Fellows, Michael R.; Vardy, Alexander; Whittle, Geoff
29
1999
The complexity of computable categoricity. Zbl 1345.03063
Downey, Rodney G.; Kach, Asher M.; Lempp, Steffen; Lewis-Pye, Andrew E. M.; Montalbán, Antonio; Turetsky, Daniel D.
28
2015
Advice classes of parametrized tractability. Zbl 0873.68071
Cai, Liming; Chen, Jianer; Downey, Rodney G.; Fellows, Michael R.
27
1997
Array nonrecursive degrees and genericity. Zbl 0849.03029
Downey, Rod; Jockusch, Carl G.; Stob, Michael
27
1996
Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems. Zbl 1270.68112
Downey, Rodney G.; Estivill-Castro, Vladimir; Fellows, Michael; Prieto, Elena; Rosamund, Frances A.
27
2003
Every low Boolean algebra is isomorphic to a recursive one. Zbl 0820.03019
Downey, Rod; Jockusch, Carl G.
26
1994
Randomness and reducibility. Zbl 1072.03024
Downey, Rod G.; Hirschfeldt, Denis R.; LaForte, Geoff
26
2004
Relativizing Chaitin’s halting probability. Zbl 1093.03025
Downey, Rod; Hirschfeldt, Denis R.; Miller, Joseph S.; Nies, André
26
2005
Parameterized approximation problems. Zbl 1154.68572
Downey, Rodney G.; Fellows, Michael R.; McCartin, Catherine
26
2006
On the parameterized complexity of short computation and factorization. Zbl 0944.68069
Cai, Liming; Chen, Jianer; Downey, Rodney G.; Fellows, Michael R.
24
1997
Automorphisms of the lattice of recursively enumerable sets: Orbits. Zbl 0758.03020
Downey, R. G.; Stob, Michael
23
1992
Schnorr randomness. Zbl 1072.03025
Downey, Rodney G.; Griffiths, Evan J.
22
2004
Array nonrecursive sets and multiple permitting arguments. Zbl 0713.03020
Downey, Rod; Jockusch, Carl; Stob, Michael
22
1990
On problems without polynomial kernels (extended abstract). Zbl 1153.68554
Bodlaender, Hans L.; Downey, Rodney G.; Fellows, Michael R.; Hermelin, Danny
22
2008
Randomness, computability, and density. Zbl 1052.68060
Downey, Rod G.; Hirschfeldt, Denis R.; Nies, André
21
2002
Strong jump-traceability. I: The computably enumerable case. Zbl 1134.03026
Cholak, Peter; Downey, Rod; Greenberg, Noam
20
2008
The parameterized complexity of some problems in logic and linguistics. Zbl 0946.03046
Downey, Rodney G.; Fellows, Michael R.; Kapron, Bruce M.; Hallett, Michael T.; Wareham, H. Todd
19
1994
Automorphisms of the lattice of \(\Pi_1^0\) classes; perfect thin classes and anc degrees. Zbl 0978.03033
Cholak, Peter; Coles, Richard; Downey, Rod; Herrmann, Eberhard
19
2001
The parameterized complexity of sequence alignment and consensus. Zbl 0888.68060
Bodlaender, Hans L.; Downey, Rodney G.; Fellows, Michael R.; Wareham, Harold T.
19
1995
Effectively categorical abelian groups. Zbl 1315.03054
Downey, Rodney; Melnikov, Alexander G.
19
2013
Asymptotic density and computably enumerable sets. Zbl 1326.03048
Downey, Rodney G.; Jockusch, Carl G. jun.; Schupp, Paul E.
18
2013
Foundations of online structure theory. Zbl 1477.03167
Bazhenov, Nikolay; Downey, Rod; Kalimullin, Iskander; Melnikov, Alexander
17
2019
Splitting theorems in recursion theory. Zbl 0792.03028
Downey, Rod; Stob, Michael
17
1993
A \(\Delta_2^0\) set with no infinite low subset in either it or its complement. Zbl 0990.03046
Downey, Rod; Hirschfeldt, Denis R.; Lempp, Steffen; Solomon, Reed
17
2001
T-degrees, jump classes, and strong reducibilities. Zbl 0638.03039
Downey, R. G.; Jockusch, C. G. jun.
17
1987
Structural interactions of the recursively enumerable T- and W-degrees. Zbl 0604.03015
Downey, R. G.; Stob, M.
16
1986
The parameterized complexity of relational database queries and an improved characterization of \(W[1]\). Zbl 0918.68018
Downey, Rod G.; Fellows, Michael R.; Taylor, Udayan
16
1997
Lowness and \(\Pi^0_2\) nullsets. Zbl 1112.03040
Downey, Rod; Nies, Andre; Weber, Rebecca; Yu, Liang
16
2006
On Schnorr and computable randomness, martingales, and machines. Zbl 1062.68064
Downey, Rod; Griffiths, Evan; Laforte, Geoffrey
15
2004
Parameterized approximation of dominating set problems. Zbl 1191.68862
Downey, Rodney G.; Fellows, Michael R.; McCartin, Catherine; Rosamond, Frances
15
2009
Lattice nonembeddings and initial segments of the recursively enumerable degrees. Zbl 0723.03025
Downey, Rod
15
1990
On presentations of algebraic structures. Zbl 0915.03039
Downey, Rodney G.
14
1997
Threshold dominating sets and an improved characterization of \(W[2]\). Zbl 0912.68075
Downey, Rodney G.; Fellows, Michael R.
14
1998
Limitwise monotonic functions and their applications. Zbl 1279.03063
Downey, Rodney G.; Kach, Asher M.; Turetsky, Daniel
14
2012
Subspaces of computable vector spaces. Zbl 1127.03036
Downey, Rodney G.; Hirschfeldt, Denis R.; Kach, Asher M.; Lempp, Steffen; Mileti, Joseph R.; Montalbán, Antonio
14
2007
Completely mitotic r. e. degrees. Zbl 0628.03028
Downey, R. G.; Slaman, T. A.
14
1989
Working with strong reducibilities above totally \(\omega \)-c.e. and array computable degrees. Zbl 1192.03014
Barmpalias, George; Downey, Rod; Greenberg, Noam
13
2010
Randomness and reducibility. Zbl 0999.03038
Downey, Rod G.; Hirschfeldt, Denis R.; LaForte, Geoff
13
2001
On the structure of parameterized problems in NP. Zbl 1096.68626
Cai, Liming; Chen, Jianer; Downey, Rodney; Fellows, Michael
13
1995
Totally \(\omega\)-computably enumerable degrees and bounding critical triples. Zbl 1149.03032
Downey, Rod; Greenberg, Noam; Weber, Rebecca
13
2007
Computable completely decomposable groups. Zbl 1341.03056
Downey, Rodney; Melnikov, Alexander G.
13
2014
The complexity of irredundant sets parameterized by size. Zbl 0948.68133
Downey, Rodney G.; Fellows, Michael R.; Raman, Venkatesh
12
2000
Fixed-parameter intractability. II. (Extended abstract). Zbl 0799.68086
Abrahamson, Karl A.; Downey, Rodney G.; Fellows, Michael R.
12
1993
Countable thin \(\Pi^0_1\) classes. Zbl 0909.03039
Cenzer, Douglas; Downey, Rodney; Jockusch, Carl; Shore, Richard A.
12
1993
Parameterized circuit complexity and the \(W\) hierarchy. Zbl 0896.68057
Downey, Rodney G.; Fellows, Michael R.; Regan, Kenneth W.
12
1998
Space complexity of abelian groups. Zbl 1161.03021
Cenzer, Douglas; Downey, Rodney G.; Remmel, Jeffrey B.; Uddin, Zia
12
2009
Kolmogorov complexity and solovay functions. Zbl 1236.68108
Bienvenu, Laurent; Downey, Rod
12
2009
Ideals in computable rings. Zbl 1127.03037
Downey, Rodney G.; Lempp, Steffen; Mileti, Joseph R.
12
2007
On choice sets and strongly non-trivial self-embeddings of recursive linear orders. Zbl 0654.03032
Downey, Rodney G.; Moses, Michael F.
12
1989
Splitting properties of r.e. sets and degrees. Zbl 0597.03025
Downey, R. G.; Welch, L. V.
11
1986
Computational tractability: The view from Mars. Zbl 0941.68577
Downey, Rodney G.; Fellows, Michael R.; Stege, Ulrike
11
1999
Highness and bounding minimal pairs. Zbl 0809.03029
Downey, Rodney G.; Lempp, Steffen; Shore, Richard A.
11
1993
On Kurtz randomness. Zbl 1070.68054
Downey, Rodney G.; Griffiths, Evan J.; Reid, Stephanie
11
2004
On initial segments of computable linear orders. Zbl 0915.03040
Coles, Richard J.; Downey, Rod; Khoussainov, Bakhadyr
11
1998
Turing degrees of reals of positive effective packing dimension. Zbl 1191.68304
Downey, Rod; Greenberg, Noam
11
2008
Minimal degrees recursive in 1-generic degrees. Zbl 0714.03037
Chong, C. T.; Downey, R. G.
11
1990
\(\Delta\)\( ^ 0_ 2\) degrees and transfer theorems. Zbl 0629.03017
Downey, R. G.
11
1987
Recursion theory and ordered groups. Zbl 0629.03020
Downey, R. G.; Kurtz, Stuart A.
11
1986
Automorphisms of supermaximal subspaces. Zbl 0572.03024
Downey, R. G.; Hird, G. R.
10
1985
The degrees of r. e. sets without the universal splitting property. Zbl 0576.03028
Downey, R. G.
10
1985
Decidable subspaces and recursively enumerable subspaces. Zbl 0585.03016
Ash, C. J.; Downey, R. G.
10
1984
On computing graph minor obstruction sets. Zbl 0952.68116
Cattell, Kevin; Dinneen, Michael J.; Downey, Rodney G.; Fellows, Michael R.; Langston, Michael A.
10
2000
Recursive linear orders with incomplete successivities. Zbl 0813.03028
Downey, Rodney G.; Moses, Michael F.
10
1991
Orderings with \(\alpha\)th jump degree 0\(^{(\alpha)}\). Zbl 0748.03027
Downey, Rodney; Knight, Julia F.
10
1992
Automorphisms of the lattice of recursively enumerable sets: Promptly simple sets. Zbl 0769.03024
Cholak, Peter; Downey, Rod; Stob, Michael
10
1992
The Kolmogorov complexity of random reals. Zbl 1065.03025
Yu, Liang; Ding, Decheng; Downey, Rodney
10
2004
Computably enumerable sets and quasi-reducibility. Zbl 0930.03049
Downey, R.; LaForte, G.; Nies, A.
10
1998
Every set has a least jump enumeration. Zbl 1023.03036
Coles, Richard J.; Downey, Rod G.; Slaman, Theodore A.
10
2000
On a question of A. Retzlaff. Zbl 0526.03028
Downey, Rod
9
1983
On \(\Pi{}^ 0_ 1\) classes and their ranked points. Zbl 0753.03016
Downey, Rod
9
1991
Minimal pairs in initial segments of the recursively enumerable degrees. Zbl 0924.03076
Downey, R.; Stob, M.
9
1997
Contiguity and distributivity in the enumerable Turing degrees. Zbl 0897.03047
Downey, Rodney G.; Lempp, Steffen
9
1997
Degree theoretic definitions of the \(\text{low}_ 2\) recursively enumerable sets. Zbl 0841.03024
Downey, Rod; Shore, Richard A.
9
1995
Strong jump-traceability. II: \(K\)-triviality. Zbl 1273.03141
Downey, Rod; Greenberg, Noam
9
2012
Computability-theoretic and proof-theoretic aspects of partial and linear orderings. Zbl 1044.03043
Downey, Rodney G.; Hirschfeldt, Denis R.; Lempp, Steffen; Solomon, Reed
9
2003
Abelian \(p\)-groups and the halting problem. Zbl 1402.03067
Downey, Rodney; Melnikov, Alexander G.; Ng, Keng Meng
8
2016
Questions in computable algebra and combinatorics. Zbl 0980.03045
Downey, Rod; Remmel, J. B.
8
2000
Jumps of hemimaximal sets. Zbl 0739.03026
Downey, Rod; Stob, Mike
8
1991
Every recursive Boolean algebra is isomorphic to one with incomplete atoms. Zbl 0796.03049
Downey, Rod
8
1993
Uniformity in computable structure theory. Zbl 1063.03018
Downey, Rod; Hirschfeldt, Denis; Khoussainov, Bakhadyr
8
2003
Computable algebras and closure systems: Coding properties. Zbl 0939.03046
Downey, R. G.; Remmel, J. B.
8
1998
Undecidability of \(L(F_{\infty})\) and other lattices of r.e. substructures. Zbl 0604.03014
Downey, R. G.
7
1986
A note on the computability of graph minor obstruction sets for monadic second order ideals. Zbl 0960.68129
Courcelle, Bruno; Downey, Rodney G.; Fellows, Michael R.
7
1997
Foundations of online structure theory. II: The operator approach. Zbl 07407778
Downey, Rod; Melnikov, Alexander; Ng, Keng Meng
1
2021
A hierarchy of Turing degrees. A transfinite hierarchy of lowness notions in the computably enumerable degrees, unifying classes, and natural definability. Zbl 07178475
Downey, Rod; Greenberg, Noam
7
2020
Graphs are not universal for online computability. Zbl 1476.03046
Downey, Rodney; Harrison-Trainor, Matthew; Kalimullin, Iskander; Melnikov, Alexander; Turetsky, Daniel
6
2020
Punctual categoricity and universality. Zbl 07333589
Downey, Rod; Greenberg, Noam; Melnikov, Alexander; Meng Ng, Keng; Turetsky, Daniel
3
2020
Enumerating abelian \(p\)-groups. Zbl 1457.03060
Downey, Rod; Melnikov, Alexander; Ng, Keng Meng
1
2020
Foundations of online structure theory. Zbl 1477.03167
Bazhenov, Nikolay; Downey, Rod; Kalimullin, Iskander; Melnikov, Alexander
17
2019
Categorical linearly ordered structures. Zbl 1435.03076
Downey, Rod; Melnikov, Alexander; Ng, Keng Meng
1
2019
Computability and randomness. Zbl 1423.03145
Downey, Rod; Hirschfeldt, Denis R.
1
2019
A hierarchy of computably enumerable degrees. Zbl 06866160
Downey, Rod; Greenberg, Noam
6
2018
Splitting into degrees with low computational strength. Zbl 1469.03117
Downey, Rod; Ng, Keng Meng
3
2018
Avoiding effective packing dimension 1 below array noncomputable c.e. degrees. Zbl 1415.03047
Downey, Rod; Stephenson, Jonathan
1
2018
On a question of Kalimullin. Zbl 06880237
Downey, Rod; Igusa, Gregory; Melnikov, Alexander
1
2018
Courcelle’s theorem for triangulations. Zbl 1353.05122
Burton, Benjamin A.; Downey, Rodney G.
4
2017
Lowness and logical depth. Zbl 1418.03150
Downey, Rod; McInerney, Michael; Ng, Keng Meng
4
2017
A Friedberg enumeration of equivalence structures. Zbl 1423.03153
Downey, Rodney G.; Melnikov, Alexander G.; Ng, Keng Meng
3
2017
Notes on computable analysis. Zbl 1420.03114
Porter, Michelle; Day, Adam; Downey, Rodney
3
2017
Any FIP real computes a 1-generic. Zbl 1423.03142
Cholak, Peter; Downey, Rodney G.; Igusa, Greg
2
2017
Corrigendum to: “On the complexity of the successivity relation in computable linear orderings”. Zbl 1375.03035
Downey, Rodney G.; Lempp, Steffen; Wu, Guohua
1
2017
Kobayashi compressibility. Zbl 1369.68249
Barmpalias, George; Downey, Rodney G.
1
2017
Abelian \(p\)-groups and the halting problem. Zbl 1402.03067
Downey, Rodney; Melnikov, Alexander G.; Ng, Keng Meng
8
2016
The finite intersection principle and genericity. Zbl 1375.03046
Diamondstone, David; Downey, Rod; Greenberg, Noam; Turetsky, Dan
3
2016
Generic Muchnik reducibility and presentations of fields. Zbl 1403.03068
Downey, Rod; Greenberg, Noam; Miller, Joseph S.
3
2016
The complexity of computable categoricity. Zbl 1345.03063
Downey, Rodney G.; Kach, Asher M.; Lempp, Steffen; Lewis-Pye, Andrew E. M.; Montalbán, Antonio; Turetsky, Daniel D.
28
2015
Asymptotic density and the Ershov hierarchy. Zbl 1361.03037
Downey, Rod; Jockusch, Carl; McNicholl, Timothy H.; Schupp, Paul
7
2015
On \(\Delta_2^0\)-categoricity of equivalence relations. Zbl 1386.03050
Downey, Rod; Melnikov, Alexander G.; Ng, Keng Meng
6
2015
Solovay functions and their applications in algorithmic randomness. Zbl 1335.03038
Bienvenu, Laurent; Downey, Rod; Nies, André; Merkle, Wolfgang
4
2015
Integer valued betting strategies and Turing degrees. Zbl 1321.03054
Barmpalias, George; Downey, Rod G.; McInerney, Michael
4
2015
Myhill-Nerode methods for hypergraphs. Zbl 1335.68098
van Bevern, René; Downey, Rodney G.; Fellows, Michael R.; Gaspers, Serge; Rosamond, Frances A.
3
2015
The members of thin and minimal \(\Pi_1^0\) classes, their ranks and Turing degrees. Zbl 1353.03042
Downey, Rodney G.; Wu, Guohua; Yang, Yue
2
2015
Computable completely decomposable groups. Zbl 1341.03056
Downey, Rodney; Melnikov, Alexander G.
13
2014
Iterated effective embeddings of abelian \(p\)-groups. Zbl 1339.03034
Downey, Rod; Melnikov, Alexander G.; Ng, Keng Meng
6
2014
Characterizing lowness for Demuth randomness. Zbl 1338.03080
Bienvenu, Laurent; Downey, Rod; Greenberg, Noam; Nies, André; Turetsky, Dan
6
2014
Turing’s legacy. Developments from Turing’s ideas in logic. Zbl 1341.03002
3
2014
Random strings and truth-table degrees of Turing complete c.e. sets. Zbl 1314.03039
Cai, Mingzhong; Downey, Rodney G.; Epstein, Rachel; Lempp, Steffen; Miller, Joseph S.
2
2014
Exact pairs for the ideal of the \(K\)-trivial sequences in the Turing degrees. Zbl 1353.03041
Barmpalias, George; Downey, Rod G.
1
2014
Fundamentals of parameterized complexity. Zbl 1358.68006
Downey, Rodney G.; Fellows, Michael R.
425
2013
Effectively categorical abelian groups. Zbl 1315.03054
Downey, Rodney; Melnikov, Alexander G.
19
2013
Asymptotic density and computably enumerable sets. Zbl 1326.03048
Downey, Rodney G.; Jockusch, Carl G. jun.; Schupp, Paul E.
18
2013
Computable categoricity versus relative computable categoricity. Zbl 1320.03070
Downey, Rodney G.; Kach, Asher M.; Lempp, Steffen; Turetsky, Daniel D.
5
2013
Pseudo-jump inversion, upper cone avoidance, and strong jump-traceability. Zbl 1267.03047
Downey, Rod; Greenberg, Noam
3
2013
Extensions of embeddings below computably enumerable degrees. Zbl 1296.03021
Downey, Rod; Greenberg, Noam; Lewis, Andrew; Montalbán, Antonio
3
2013
Proceedings of the 12th Asian logic conference, Wellington, New Zealand, December 15–20, 2011. Zbl 1318.03005
1
2013
Limitwise monotonic functions and their applications. Zbl 1279.03063
Downey, Rodney G.; Kach, Asher M.; Turetsky, Daniel
14
2012
Strong jump-traceability. II: \(K\)-triviality. Zbl 1273.03141
Downey, Rod; Greenberg, Noam
9
2012
Bounded randomness. Zbl 1353.03045
Brodhead, Paul; Downey, Rod; Ng, Keng Meng
5
2012
The multivariate algorithmic revolution and beyond. Essays dedicated to Michael R. Fellows on the occasion of his 60th birthday. Zbl 1245.68001
4
2012
The birth and early years of parameterized complexity. Zbl 1358.68129
Downey, Rod
3
2012
A basic parameterized complexity primer. Zbl 1358.68130
Downey, Rod
2
2012
Randomness, computation and mathematics. Zbl 1358.03058
Downey, Rod
1
2012
Jump inversions inside effectively closed sets and applications to randomness. Zbl 1248.03065
Barmpalias, George; Downey, Rod; Ng, Keng Meng
6
2011
Confronting intractability via parameters. Zbl 1298.68094
Downey, Rodney G.; Thilikos, Dimitrios M.
5
2011
Binary subtrees with few labeled paths. Zbl 1265.05593
Downey, Rodney G.; Greenberg, Noam; Jockusch, Carl G. jun.; Milans, Kevin G.
5
2011
Limits on jump inversion for strong reducibilities. Zbl 1248.03062
Csima, Barbara F.; Downey, Rod; Ng, Keng Meng
4
2011
Euclidean functions of computable Euclidean domains. Zbl 1260.03082
Downey, Rodney G.; Kach, Asher M.
2
2011
Algorithmic randomness and complexity. Zbl 1221.68005
Downey, Rodney G.; Hirschfeldt, Denis R.
349
2010
Working with strong reducibilities above totally \(\omega \)-c.e. and array computable degrees. Zbl 1192.03014
Barmpalias, George; Downey, Rod; Greenberg, Noam
13
2010
Decidability and computability of certain torsion-free abelian groups. Zbl 1211.03063
Downey, Rodney G.; Goncharov, Sergei S.; Kach, Asher M.; Knight, Julia F.; Kudinov, Oleg V.; Melnikov, Alexander G.; Turetsky, Daniel
6
2010
On the complexity of the successivity relation in computable linear orderings. Zbl 1256.03039
Downey, Rod; Lempp, Steffen; Wu, Guohua
6
2010
Effective packing dimension and traceability. Zbl 1204.03042
Downey, Rod; Ng, Keng Meng
2
2010
On problems without polynomial kernels. Zbl 1192.68288
Bodlaender, Hans L.; Downey, Rodney G.; Fellows, Michael R.; Hermelin, Danny
179
2009
Parameterized approximation of dominating set problems. Zbl 1191.68862
Downey, Rodney G.; Fellows, Michael R.; McCartin, Catherine; Rosamond, Frances
15
2009
Space complexity of abelian groups. Zbl 1161.03021
Cenzer, Douglas; Downey, Rodney G.; Remmel, Jeffrey B.; Uddin, Zia
12
2009
Kolmogorov complexity and solovay functions. Zbl 1236.68108
Bienvenu, Laurent; Downey, Rod
12
2009
\(K\)-trivial degrees and the jump-traceability hierarchy. Zbl 1165.03024
Barmpalias, George; Downey, Rod; Greenberg, Noam
6
2009
On computable self-embeddings of computable linear orderings. Zbl 1201.03029
Downey, Rodney G.; Kastermans, Bart; Lempp, Steffen
5
2009
Lowness for Demuth randomness. Zbl 1268.03053
Downey, Rod; Ng, Keng Meng
2
2009
The sixth lecture on algorithmic randomness. Zbl 1208.03044
Downey, Rod
1
2009
The isomorphism problem for torsion-free abelian groups is analytic complete. Zbl 1156.03042
Downey, Rod; Montalbán, Antonio
31
2008
On problems without polynomial kernels (extended abstract). Zbl 1153.68554
Bodlaender, Hans L.; Downey, Rodney G.; Fellows, Michael R.; Hermelin, Danny
22
2008
Strong jump-traceability. I: The computably enumerable case. Zbl 1134.03026
Cholak, Peter; Downey, Rod; Greenberg, Noam
20
2008
Turing degrees of reals of positive effective packing dimension. Zbl 1191.68304
Downey, Rod; Greenberg, Noam
11
2008
Lowness for computable machines. Zbl 1175.03025
Downey, Rod; Greenberg, Noam; Mihailović, Nenad; Nies, André
5
2008
On the orbits of computably enumerable sets. Zbl 1214.03028
Cholak, Peter A.; Downey, Rodney; Harrington, Leo A.
4
2008
Five lectures on algorithmic randomness. Zbl 1178.03058
Downey, Rod
1
2008
The complexity of orbits of computably enumerable sets. Zbl 1142.03022
Cholak, Peter A.; Downey, Rodney; Harrington, Leo A.
1
2008
Slender classes. Zbl 1145.03019
Downey, Rod; Montalbán, Antonio
1
2008
Prompt simplicity, array computability and cupping. Zbl 1156.03041
Downey, Rod; Greenberg, Noam; Miller, Joseph S.; Weber, Rebecca
1
2008
The upward closure of a perfect thin class. Zbl 1153.03018
Downey, Rod; Greenberg, Noam; Miller, Joseph S.
1
2008
Subspaces of computable vector spaces. Zbl 1127.03036
Downey, Rodney G.; Hirschfeldt, Denis R.; Kach, Asher M.; Lempp, Steffen; Mileti, Joseph R.; Montalbán, Antonio
14
2007
Totally \(\omega\)-computably enumerable degrees and bounding critical triples. Zbl 1149.03032
Downey, Rod; Greenberg, Noam; Weber, Rebecca
13
2007
Ideals in computable rings. Zbl 1127.03037
Downey, Rodney G.; Lempp, Steffen; Mileti, Joseph R.
12
2007
Online promise problems with online width metrics. Zbl 1178.68375
Downey, Rodney G.; McCartin, Catherine
3
2007
Undecidability of the structure of the Solovay degrees of c.e. reals. Zbl 1115.03046
Downey, Rod; Hirschfeldt, Denis R.; LaForte, Geoff
1
2007
Bounded fixed-parameter tractability and reducibility. Zbl 1149.03031
Downey, Rod; Flum, Jörg; Grohe, Martin; Weyer, Mark
1
2007
Calibrating randomness. Zbl 1113.03037
Downey, Rod; Hirschfeldt, Dennis R.; Nies, André; Terwijn, Sebastiaan A.
42
2006
Parameterized approximation problems. Zbl 1154.68572
Downey, Rodney G.; Fellows, Michael R.; McCartin, Catherine
26
2006
Lowness and \(\Pi^0_2\) nullsets. Zbl 1112.03040
Downey, Rod; Nies, Andre; Weber, Rebecca; Yu, Liang
16
2006
A basis theorem for \(\Pi_1^0\) classes of positive measure and jump inversion for random reals. Zbl 1085.03032
Downey, Rod; Miller, Joseph S.
4
2006
Schnorr dimension. Zbl 1125.03033
Downey, Rodney; Merkle, Wolfgang; Reimann, Jan
2
2006
Totally \(< \omega^{ \omega }\) computably enumerable and \(m\)-topped degrees. Zbl 1109.03039
Downey, Rod; Greenberg, Noam
2
2006
On self-embeddings of computable linear orderings. Zbl 1105.03036
Downey, Rodney G.; Jockusch, Carl; Miller, Joseph S.
2
2006
Every 1-generic computes a properly 1-generic. Zbl 1117.03052
Csima, Barbara F.; Downey, Rod; Greenberg, Noam; Hirschfeldt, Denis R.; Miller, Joseph S.
1
2006
Algorithmic randomness and computability. Zbl 1100.68042
Downey, Rod
1
2006
Arithmetical Sacks forcing. Zbl 1103.03040
Downey, Rod; Yu, Liang
1
2006
Mathematical logic in Asia. Proceedings of the 9th Asian logic conference, Novosibirsk, Russia, August 16–19, 2005. Zbl 1105.03004
1
2006
Relativizing Chaitin’s halting probability. Zbl 1093.03025
Downey, Rod; Hirschfeldt, Denis R.; Miller, Joseph S.; Nies, André
26
2005
Some computability-theoretic aspects of reals and randomness. Zbl 1075.03020
Downey, Rodney G.
7
2005
Completing pseudojump operators. Zbl 1085.03031
Coles, R.; Downey, R.; Jockusch, C.; LaForte, G.
3
2005
Schnorr dimension. Zbl 1113.03331
Downey, Rodney; Merkle, Wolfgang; Reimann, Jan
2
2005
Randomness and reducibility. Zbl 1072.03024
Downey, Rod G.; Hirschfeldt, Denis R.; LaForte, Geoff
26
2004
...and 142 more Documents
all top 5

Cited by 1,815 Authors

155 Downey, Rodney Graham
82 Saurabh, Saket
63 Niedermeier, Rolf
51 Golovach, Petr A.
48 Fomin, Fedor V.
47 Fellows, Michael Ralph
46 Gutin, Gregory Z.
43 Melnikov, Alexander G.
42 Nies, André Otfrid
38 Greenberg, Noam
38 Ng, KengMeng
37 Chen, Jian-er
35 Lokshtanov, Daniel
34 Barmpalias, George
34 Fernau, Henning
34 Kratsch, Stefan
32 Stephan, Frank
31 Raman, Venkatesh
30 Guo, Jiong
30 Thilikos, Dimitrios M.
30 Zehavi, Meirav
29 Lempp, Steffen
29 Miller, Joseph S.
29 Montalbán, Antonio
29 Sau, Ignasi
29 Szeider, Stefan
28 Komusiewicz, Christian
26 Kanj, Iyad A.
25 Yeo, Anders
24 Bienvenu, Laurent
24 Hermelin, Danny
23 Ganian, Robert
23 Jansen, Bart M. P.
23 Ordyniak, Sebastian
23 Wu, Guohua
22 Cholak, Peter A.
22 Paschos, Vangelis Th.
22 Wang, Jianxin
21 Dondi, Riccardo
21 Heggernes, Pinar
21 Pilipczuk, Marcin L.
21 Pilipczuk, Michał
20 Bazhenov, Nikolaĭ Alekseevich
20 Wahlström, Magnus
19 Bodlaender, Hans L.
19 Kalimullin, Iskander Shagitovich
19 Yu, Liang
18 Bredereck, Robert
18 Calude, Cristian S.
18 Hirschfeldt, Denis Roman
18 Jockusch, Carl G. jun.
18 Van Leeuwen, Erik Jan
17 Cygan, Marek
17 Misra, Neeldhara
17 Nichterlein, André
17 Panolan, Fahad
17 Paul, Christophe
17 Ramanujan, M. S.
17 Sorge, Manuel
17 Xia, Ge
16 Feng, Qilong
16 Harizanov, Valentina S.
16 Kratsch, Dieter
16 Marx, Dániel
16 Rosamond, Frances A.
16 Rossmanith, Peter
16 Shore, Richard Arnold
16 van Bevern, René
15 Gaspers, Serge
15 Paulusma, Daniël
15 Slaman, Theodore A.
14 Courcelle, Bruno
14 Harrison-Trainor, Matthew
14 Lampis, Michael
14 Liedloff, Mathieu
14 Philip, Geevarghese
14 van ’t Hof, Pim
14 Villanger, Yngve
13 Eiben, Eduard
13 Franklin, Johanna N. Y.
13 Sikora, Florian
13 Suchý, Ondřej
12 Abu-Khzam, Faisal N.
12 Bonnet, Edouard
12 Cenzer, Douglas
12 Fertin, Guillaume
12 Merkle, Wolfgang
12 Patey, Ludovic
12 Turetsky, Daniel D.
11 Bazgan, Cristina
11 Escoffier, Bruno
11 Flum, Jörg
11 Hölzl, Rupert
11 Kim, Eun Jung
11 Lewis, Andrew E. M.
11 Miyabe, Kenshi
11 Mnich, Matthias
11 Sikdar, Somnath
11 Solomon, Reed
11 Vialette, Stéphane
...and 1,715 more Authors
all top 5

Cited in 153 Serials

315 Theoretical Computer Science
151 Annals of Pure and Applied Logic
141 Journal of Computer and System Sciences
136 Algorithmica
129 The Journal of Symbolic Logic
126 Discrete Applied Mathematics
76 Theory of Computing Systems
74 Information Processing Letters
56 Information and Computation
44 Journal of Discrete Algorithms
41 Archive for Mathematical Logic
40 The Bulletin of Symbolic Logic
37 SIAM Journal on Discrete Mathematics
34 Transactions of the American Mathematical Society
32 Proceedings of the American Mathematical Society
27 Notre Dame Journal of Formal Logic
26 Discrete Optimization
25 Artificial Intelligence
22 Algebra and Logic
19 Journal of Combinatorial Optimization
18 Mathematical Logic Quarterly (MLQ)
18 Journal of Mathematical Logic
17 Advances in Mathematics
15 Computability
12 SIAM Journal on Computing
11 Journal of Algebra
11 Operations Research Letters
11 Russian Mathematics
10 Discrete Mathematics
10 Israel Journal of Mathematics
10 Siberian Mathematical Journal
9 European Journal of Operational Research
9 Lobachevskii Journal of Mathematics
8 Annals of Mathematics and Artificial Intelligence
7 Journal of Combinatorial Theory. Series B
7 European Journal of Combinatorics
7 MSCS. Mathematical Structures in Computer Science
7 Journal of Scheduling
7 Computer Science Review
6 Logical Methods in Computer Science
5 Journal of the American Mathematical Society
5 Annals of Operations Research
5 Computational Geometry
5 Journal of Mathematical Sciences (New York)
5 Journal of Logic and Analysis
4 Mathematical Social Sciences
4 Journal of Complexity
4 International Journal of Approximate Reasoning
4 The Journal of Artificial Intelligence Research (JAIR)
4 Journal of Graph Algorithms and Applications
4 Algorithms
4 ACM Transactions on Computation Theory
4 Prikladnaya Diskretnaya Matematika
3 Acta Informatica
3 Journal of Mathematical Physics
3 Journal of Mathematical Psychology
3 Order
3 Discrete & Computational Geometry
3 Computers & Operations Research
3 Journal of Automated Reasoning
3 International Journal of Algebra and Computation
3 Mathematical Programming. Series A. Series B
3 Computational Complexity
3 Constraints
3 Acta Mathematica Sinica. English Series
3 Natural Computing
3 Sibirskie Èlektronnye Matematicheskie Izvestiya
3 RAIRO. Theoretical Informatics and Applications
2 Journal of Statistical Physics
2 Applied Mathematics and Computation
2 Fundamenta Mathematicae
2 Fuzzy Sets and Systems
2 Advances in Applied Mathematics
2 Statistics & Probability Letters
2 Social Choice and Welfare
2 Journal of Computer Science and Technology
2 International Journal of Foundations of Computer Science
2 International Journal of Computer Mathematics
2 Stochastic Processes and their Applications
2 New Zealand Journal of Mathematics
2 The Electronic Journal of Combinatorics
2 Journal of the ACM
2 Philosophical Transactions of the Royal Society of London. Series A. Mathematical, Physical and Engineering Sciences
2 RAIRO. Operations Research
2 ACM Transactions on Computational Logic
2 ACM Journal of Experimental Algorithmics
2 Oberwolfach Reports
2 Discrete Mathematics, Algorithms and Applications
1 Archiv für Mathematische Logik und Grundlagenforschung
1 Communications in Mathematical Physics
1 International Journal of Systems Science
1 Journal of Mathematical Biology
1 Mathematical Biosciences
1 Mathematical Notes
1 Physics Reports
1 Mathematics of Computation
1 Bulletin of Mathematical Biology
1 ACM Transactions on Mathematical Software
1 Computing
1 Journal of Combinatorial Theory. Series A
...and 53 more Serials
all top 5

Cited in 40 Fields

1,403 Computer science (68-XX)
834 Mathematical logic and foundations (03-XX)
750 Combinatorics (05-XX)
196 Operations research, mathematical programming (90-XX)
98 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
61 Biology and other natural sciences (92-XX)
52 Order, lattices, ordered algebraic structures (06-XX)
30 Group theory and generalizations (20-XX)
23 Probability theory and stochastic processes (60-XX)
22 Information and communication theory, circuits (94-XX)
19 Measure and integration (28-XX)
15 General and overarching topics; collections (00-XX)
11 Number theory (11-XX)
11 Statistics (62-XX)
11 Quantum theory (81-XX)
10 History and biography (01-XX)
10 Dynamical systems and ergodic theory (37-XX)
10 Statistical mechanics, structure of matter (82-XX)
8 Real functions (26-XX)
8 General topology (54-XX)
7 Convex and discrete geometry (52-XX)
7 Numerical analysis (65-XX)
6 Manifolds and cell complexes (57-XX)
5 Field theory and polynomials (12-XX)
5 Commutative algebra (13-XX)
5 Linear and multilinear algebra; matrix theory (15-XX)
5 Functional analysis (46-XX)
4 General algebraic systems (08-XX)
3 Algebraic geometry (14-XX)
3 Associative rings and algebras (16-XX)
3 Category theory; homological algebra (18-XX)
3 Harmonic analysis on Euclidean spaces (42-XX)
3 Geometry (51-XX)
2 Abstract harmonic analysis (43-XX)
2 Operator theory (47-XX)
2 Calculus of variations and optimal control; optimization (49-XX)
2 Systems theory; control (93-XX)
1 Several complex variables and analytic spaces (32-XX)
1 Partial differential equations (35-XX)
1 Algebraic topology (55-XX)

Citations by Year

Wikidata Timeline

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.