×

zbMATH — the first resource for mathematics

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: 292 Publications since 1983, including 17 Books
Reviewing Activity: 118 Reviews
Biographic References: 8 Publications
all top 5

Co-Authors

56 single-authored
34 Fellows, Michael Ralph
21 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 A.
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 Khoussainov, Bakhadyr M.
3 LaForte, Geoff
3 Moses, Michael F.
3 Slaman, Theodore A.
3 Weber, Rebecca
2 Abrahamson, Karl A.
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 Harrison-Trainor, Matthew
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 Rosamond, Frances A.
2 Schupp, Paul E.
2 Stege, Ulrike
2 Stephan, Frank
2 Terwijn, Sebastiaan A.
2 Turetsky, Dan
2 Welch, Lawrence V.
2 Yang, Yue
1 Ambos-Spies, Klaus
1 Arai, Toshiyasu
1 Ash, Christopher John
1 Bailey, Colin G.
1 Bazhenov, Nikolaĭ Alekseevich
1 Berrick, A. Jon
1 Blaylock, Rich
1 Brodhead, Paul
1 Burton, Benjamin A.
1 Cai, Mingzhong
1 Cattell, Kevin
1 Chih, Ellen S.
1 Conder, Marston D. E.
1 Courcelle, Bruno
1 Day, Adam R.
1 Dehne, Frank
1 Diamondstone, David E.
1 Dinneen, Michael J.
1 Epstein, Rachel
1 Estivill-Castro, Vladimir
1 Feng, Qi
1 Flum, Jörg
1 Fomin, Fedor V.
1 Furedi, Zoltan
1 Gale, Amy
1 Gasarch, William Ian
1 Gaspers, Serge
1 Gauld, David B.
1 Grohe, Martin
1 Hallett, Michael T.
1 Hammatt, Ellen
1 Haught, Christine Ann
1 Hird, Geoffrey R.
1 Igusa, Greg
1 Igusa, Gregory
1 Kalantari, Iraj
1 Kapron, Bruce M.
...and 41 more Co-Authors
all top 5

Serials

41 Annals of Pure and Applied Logic
28 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
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
2 Computability
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 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 Texts in Computer Science

Publications by Year

Citations contained in zbMATH Open

240 Publications have been cited 3,633 times in 2,114 Documents Cited by Year
Parameterized complexity. Zbl 0914.68076
Downey, R. G.; Fellows, M. R.
474
1998
Fundamentals of parameterized complexity. Zbl 1358.68006
Downey, Rodney G.; Fellows, Michael R.
374
2013
Algorithmic randomness and complexity. Zbl 1221.68005
Downey, Rodney G.; Hirschfeldt, Denis R.
320
2010
On problems without polynomial kernels. Zbl 1192.68288
Bodlaender, Hans L.; Downey, Rodney G.; Fellows, Michael R.; Hermelin, Danny
173
2009
Fixed-parameter tractability and completeness II: On completeness for W[1]. Zbl 0873.68059
Downey, Rod G.; Fellows, Michael R.
118
1995
Parameterized complexity after (almost) ten years: Review and open questions. Zbl 0961.68533
Downey, Rodney G.; Fellows, Michael R.
100
1999
Fixed-parameter tractability and completeness. I: Basic results. Zbl 0830.68063
Downey, Rod G.; Fellows, Michael R.
98
1995
Parametrized complexity: A framework for systematically confronting computational intractability. Zbl 0935.68046
Downey, Rodney G.; Fellows, Michael R.; Stege, Ulrike
51
1999
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.
50
1995
Fixed-parameter tractability and completeness. Zbl 0768.68136
Downey, Rod G.; Fellows, Michael R.
48
1992
Calibrating randomness. Zbl 1113.03037
Downey, Rod; Hirschfeldt, Dennis R.; Nies, André; Terwijn, Sebastiaan A.
41
2006
Parameterized computational feasibility. Zbl 0834.68046
Downey, Rodney G.; Fellows, Michael R.
41
1995
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
The isomorphism problem for torsion-free abelian groups is analytic complete. Zbl 1156.03042
Downey, Rod; Montalbán, Antonio
31
2008
Trivial reals. Zbl 1044.03027
Downey, Rod G.; Hirschfeldt, Denis R.; Nies, André; Stephan, Frank
31
2003
Fixed-parameter tractability and completeness. III: Some structural aspects of the \(W\) hierarchy. Zbl 0799.68087
Downey, Rod; Fellows, Michael
30
1993
The parametrized complexity of some fundamental problems in coding theory. Zbl 0943.68079
Downey, Rod G.; Fellows, Michael R.; Vardy, Alexander; Whittle, Geoff
28
1999
Advice classes of parametrized tractability. Zbl 0873.68071
Cai, Liming; Chen, Jianer; Downey, Rodney G.; Fellows, Michael R.
27
1997
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é
25
2005
Parameterized approximation problems. Zbl 1154.68572
Downey, Rodney G.; Fellows, Michael R.; McCartin, Catherine
25
2006
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.
25
2015
Every low Boolean algebra is isomorphic to a recursive one. Zbl 0820.03019
Downey, Rod; Jockusch, Carl G.
25
1994
Array nonrecursive degrees and genericity. Zbl 0849.03029
Downey, Rod; Jockusch, Carl G.; Stob, Michael
25
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.
24
2003
Automorphisms of the lattice of recursively enumerable sets: Orbits. Zbl 0758.03020
Downey, R. G.; Stob, Michael
23
1992
On the parameterized complexity of short computation and factorization. Zbl 0944.68069
Cai, Liming; Chen, Jianer; Downey, Rodney G.; Fellows, Michael R.
23
1997
On problems without polynomial kernels (extended abstract). Zbl 1153.68554
Bodlaender, Hans L.; Downey, Rodney G.; Fellows, Michael R.; Hermelin, Danny
22
2008
Array nonrecursive sets and multiple permitting arguments. Zbl 0713.03020
Downey, Rod; Jockusch, Carl; Stob, Michael
21
1990
Strong jump-traceability. I: The computably enumerable case. Zbl 1134.03026
Cholak, Peter; Downey, Rod; Greenberg, Noam
20
2008
Schnorr randomness. Zbl 1072.03025
Downey, Rodney G.; Griffiths, Evan J.
20
2004
Randomness, computability, and density. Zbl 1052.68060
Downey, Rod G.; Hirschfeldt, Denis R.; Nies, André
19
2002
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 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
Effectively categorical abelian groups. Zbl 1315.03054
Downey, Rodney; Melnikov, Alexander G.
19
2013
The parameterized complexity of sequence alignment and consensus. Zbl 0888.68060
Bodlaender, Hans L.; Downey, Rodney G.; Fellows, Michael R.; Wareham, Harold T.
18
1995
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
Asymptotic density and computably enumerable sets. Zbl 1326.03048
Downey, Rodney G.; Jockusch, Carl G. jun.; Schupp, Paul E.
16
2013
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
T-degrees, jump classes, and strong reducibilities. Zbl 0638.03039
Downey, R. G.; Jockusch, C. G. jun.
16
1987
On Schnorr and computable randomness, martingales, and machines. Zbl 1062.68064
Downey, Rod; Griffiths, Evan; Laforte, Geoffrey
15
2004
Lattice nonembeddings and initial segments of the recursively enumerable degrees. Zbl 0723.03025
Downey, Rod
15
1990
Parameterized approximation of dominating set problems. Zbl 1191.68862
Downey, Rodney G.; Fellows, Michael R.; McCartin, Catherine; Rosamond, Frances
15
2009
Lowness and \(\Pi^0_2\) nullsets. Zbl 1112.03040
Downey, Rod; Nies, Andre; Weber, Rebecca; Yu, Liang
14
2006
On presentations of algebraic structures. Zbl 0915.03039
Downey, Rodney G.
14
1997
Completely mitotic r. e. degrees. Zbl 0628.03028
Downey, R. G.; Slaman, T. A.
14
1989
On the structure of parameterized problems in NP. Zbl 1096.68626
Cai, Liming; Chen, Jianer; Downey, Rodney; Fellows, Michael
13
1995
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
13
2007
Computable completely decomposable groups. Zbl 1341.03056
Downey, Rodney; Melnikov, Alexander G.
13
2014
Randomness and reducibility. Zbl 0999.03038
Downey, Rod G.; Hirschfeldt, Denis R.; LaForte, Geoff
13
2001
Threshold dominating sets and an improved characterization of \(W[2]\). Zbl 0912.68075
Downey, Rodney G.; Fellows, Michael R.
13
1998
Working with strong reducibilities above totally \(\omega \)-c.e. and array computable degrees. Zbl 1192.03014
Barmpalias, George; Downey, Rod; Greenberg, Noam
13
2010
Limitwise monotonic functions and their applications. Zbl 1279.03063
Downey, Rodney G.; Kach, Asher M.; Turetsky, Daniel
13
2012
Countable thin \(\Pi^0_1\) classes. Zbl 0909.03039
Cenzer, Douglas; Downey, Rodney; Jockusch, Carl; Shore, Richard A.
12
1993
Fixed-parameter intractability. II. (Extended abstract). Zbl 0799.68086
Abrahamson, Karl A.; Downey, Rodney G.; Fellows, Michael R.
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
On choice sets and strongly non-trivial self-embeddings of recursive linear orders. Zbl 0654.03032
Downey, Rodney G.; Moses, Michael F.
12
1989
Foundations of online structure theory. Zbl 07087944
Bazhenov, Nikolay; Downey, Rod; Kalimullin, Iskander; Melnikov, Alexander
12
2019
Totally \(\omega\)-computably enumerable degrees and bounding critical triples. Zbl 1149.03032
Downey, Rod; Greenberg, Noam; Weber, Rebecca
11
2007
Highness and bounding minimal pairs. Zbl 0809.03029
Downey, Rodney G.; Lempp, Steffen; Shore, Richard A.
11
1993
Splitting properties of r.e. sets and degrees. Zbl 0597.03025
Downey, R. G.; Welch, L. V.
11
1986
On initial segments of computable linear orders. Zbl 0915.03040
Coles, Richard J.; Downey, Rod; Khoussainov, Bakhadyr
11
1998
Computational tractability: The view from Mars. Zbl 0941.68577
Downey, Rodney G.; Fellows, Michael R.; Stege, Ulrike
11
1999
The complexity of irredundant sets parameterized by size. Zbl 0948.68133
Downey, Rodney G.; Fellows, Michael R.; Raman, Venkatesh
11
2000
\(\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
Turing degrees of reals of positive effective packing dimension. Zbl 1191.68304
Downey, Rod; Greenberg, Noam
11
2008
Kolmogorov complexity and solovay functions. Zbl 1236.68108
Bienvenu, Laurent; Downey, Rod
11
2009
Ideals in computable rings. Zbl 1127.03037
Downey, Rodney G.; Lempp, Steffen; Mileti, Joseph R.
10
2007
Computably enumerable sets and quasi-reducibility. Zbl 0930.03049
Downey, R.; LaForte, G.; Nies, A.
10
1998
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
Every set has a least jump enumeration. Zbl 1023.03036
Coles, Richard J.; Downey, Rod G.; Slaman, Theodore A.
10
2000
On Kurtz randomness. Zbl 1070.68054
Downey, Rodney G.; Griffiths, Evan J.; Reid, Stephanie
10
2004
The Kolmogorov complexity of random reals. Zbl 1065.03025
Yu, Liang; Ding, Decheng; Downey, Rodney
10
2004
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
Minimal degrees recursive in 1-generic degrees. Zbl 0714.03037
Chong, C. T.; Downey, R. G.
10
1990
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
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
On computing graph minor obstruction sets. Zbl 0952.68116
Cattell, Kevin; Dinneen, Michael J.; Downey, Rodney G.; Fellows, Michael R.; Langston, Michael A.
9
2000
Strong jump-traceability. II: \(K\)-triviality. Zbl 1273.03141
Downey, Rod; Greenberg, Noam
9
2012
Computable algebras and closure systems: Coding properties. Zbl 0939.03046
Downey, R. G.; Remmel, J. B.
8
1998
Degree theoretic definitions of the \(\text{low}_ 2\) recursively enumerable sets. Zbl 0841.03024
Downey, Rod; Shore, Richard A.
8
1995
Every recursive Boolean algebra is isomorphic to one with incomplete atoms. Zbl 0796.03049
Downey, Rod
8
1993
Jumps of hemimaximal sets. Zbl 0739.03026
Downey, Rod; Stob, Mike
8
1991
Uniformity in computable structure theory. Zbl 1063.03018
Downey, Rod; Hirschfeldt, Denis; Khoussainov, Bakhadyr
8
2003
Contiguity and distributivity in the enumerable Turing degrees. Zbl 0897.03047
Downey, Rodney G.; Lempp, Steffen
8
1997
Questions in computable algebra and combinatorics. Zbl 0980.03045
Downey, Rod; Remmel, J. B.
8
2000
Abelian \(p\)-groups and the halting problem. Zbl 1402.03067
Downey, Rodney; Melnikov, Alexander G.; Ng, Keng Meng
8
2016
Some computability-theoretic aspects of reals and randomness. Zbl 1075.03020
Downey, Rodney G.
7
2005
Friedberg splittings of recursively enumerable sets. Zbl 0795.03057
Downey, Rod; Stob, Michael
7
1993
Graphs are not universal for online computability. Zbl 07210414
Downey, Rodney; Harrison-Trainor, Matthew; Kalimullin, Iskander; Melnikov, Alexander; Turetsky, Daniel
6
2020
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
4
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 07087944
Bazhenov, Nikolay; Downey, Rod; Kalimullin, Iskander; Melnikov, Alexander
12
2019
Categorical linearly ordered structures. Zbl 1435.03076
Downey, Rod; Melnikov, Alexander; Ng, Keng Meng
1
2019
A hierarchy of computably enumerable degrees. Zbl 06866160
Downey, Rod; Greenberg, Noam
5
2018
Splitting into degrees with low computational strength. Zbl 1469.03117
Downey, Rod; Ng, Keng Meng
3
2018
On a question of Kalimullin. Zbl 06880237
Downey, Rod; Igusa, Gregory; Melnikov, Alexander
1
2018
Avoiding effective packing dimension 1 below array noncomputable c.e. degrees. Zbl 1415.03047
Downey, Rod; Stephenson, Jonathan
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
Any FIP real computes a 1-generic. Zbl 1423.03142
Cholak, Peter; Downey, Rodney G.; Igusa, Greg
2
2017
Kobayashi compressibility. Zbl 1369.68249
Barmpalias, George; Downey, Rodney G.
1
2017
Notes on computable analysis. Zbl 1420.03114
Porter, Michelle; Day, Adam; Downey, Rodney
1
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
Abelian \(p\)-groups and the halting problem. Zbl 1402.03067
Downey, Rodney; Melnikov, Alexander G.; Ng, Keng Meng
8
2016
Generic Muchnik reducibility and presentations of fields. Zbl 1403.03068
Downey, Rod; Greenberg, Noam; Miller, Joseph S.
3
2016
The finite intersection principle and genericity. Zbl 1375.03046
Diamondstone, David; Downey, Rod; Greenberg, Noam; Turetsky, Dan
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.
25
2015
Asymptotic density and the Ershov hierarchy. Zbl 1361.03037
Downey, Rod; Jockusch, Carl; McNicholl, Timothy H.; Schupp, Paul
6
2015
On \(\Delta_2^0\)-categoricity of equivalence relations. Zbl 1386.03050
Downey, Rod; Melnikov, Alexander G.; Ng, Keng Meng
6
2015
Integer valued betting strategies and Turing degrees. Zbl 1321.03054
Barmpalias, George; Downey, Rod G.; McInerney, Michael
4
2015
Solovay functions and their applications in algorithmic randomness. Zbl 1335.03038
Bienvenu, Laurent; Downey, Rod; Nies, André; Merkle, Wolfgang
3
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
Characterizing lowness for Demuth randomness. Zbl 1338.03080
Bienvenu, Laurent; Downey, Rod; Greenberg, Noam; Nies, André; Turetsky, Dan
6
2014
Iterated effective embeddings of abelian \(p\)-groups. Zbl 1339.03034
Downey, Rod; Melnikov, Alexander G.; Ng, Keng Meng
6
2014
Turing’s legacy. Developments from Turing’s ideas in logic. Zbl 1341.03002
Downey, Rod
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.
374
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.
16
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
Downey, Rod; Brendle, Jörg; Goldblatt, Robert; Kim, Byunghan
1
2013
Limitwise monotonic functions and their applications. Zbl 1279.03063
Downey, Rodney G.; Kach, Asher M.; Turetsky, Daniel
13
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
Bodlaender, Hans L.; Downey, Rod; Fomin, Fedor V.; Marx, Dániel
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.
4
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.
320
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
173
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
11
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
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
Five lectures on algorithmic randomness. Zbl 1178.03058
Downey, Rod
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
13
2007
Totally \(\omega\)-computably enumerable degrees and bounding critical triples. Zbl 1149.03032
Downey, Rod; Greenberg, Noam; Weber, Rebecca
11
2007
Ideals in computable rings. Zbl 1127.03037
Downey, Rodney G.; Lempp, Steffen; Mileti, Joseph R.
10
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.
41
2006
Parameterized approximation problems. Zbl 1154.68572
Downey, Rodney G.; Fellows, Michael R.; McCartin, Catherine
25
2006
Lowness and \(\Pi^0_2\) nullsets. Zbl 1112.03040
Downey, Rod; Nies, Andre; Weber, Rebecca; Yu, Liang
14
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
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
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
Goncharov, S. S.; Downey, R.; Ono, H.
1
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
Schnorr dimension. Zbl 1125.03033
Downey, Rodney; Merkle, Wolfgang; Reimann, Jan
1
2006
Relativizing Chaitin’s halting probability. Zbl 1093.03025
Downey, Rod; Hirschfeldt, Denis R.; Miller, Joseph S.; Nies, André
25
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
Schnorr randomness. Zbl 1072.03025
Downey, Rodney G.; Griffiths, Evan J.
20
2004
On Schnorr and computable randomness, martingales, and machines. Zbl 1062.68064
Downey, Rod; Griffiths, Evan; Laforte, Geoffrey
15
2004
...and 140 more Documents
all top 5

Cited by 1,718 Authors

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

Cited in 148 Serials

301 Theoretical Computer Science
148 Annals of Pure and Applied Logic
133 Journal of Computer and System Sciences
129 Algorithmica
124 Discrete Applied Mathematics
122 The Journal of Symbolic Logic
71 Information Processing Letters
71 Theory of Computing Systems
52 Information and Computation
44 Journal of Discrete Algorithms
40 Archive for Mathematical Logic
38 The Bulletin of Symbolic Logic
34 Transactions of the American Mathematical Society
33 SIAM Journal on Discrete Mathematics
32 Proceedings of the American Mathematical Society
26 Notre Dame Journal of Formal Logic
26 Discrete Optimization
21 Algebra and Logic
19 Artificial Intelligence
19 Journal of Combinatorial Optimization
18 Mathematical Logic Quarterly (MLQ)
18 Journal of Mathematical Logic
17 Advances in Mathematics
11 Journal of Algebra
10 Discrete Mathematics
10 Siberian Mathematical Journal
10 Operations Research Letters
9 Israel Journal of Mathematics
9 SIAM Journal on Computing
9 European Journal of Operational Research
9 Russian Mathematics
9 Computability
8 Lobachevskii Journal of Mathematics
7 Journal of Combinatorial Theory. Series B
7 European Journal of Combinatorics
7 MSCS. Mathematical Structures in Computer Science
7 Annals of Mathematics and Artificial Intelligence
7 Journal of Scheduling
6 Computer Science Review
5 Computational Geometry
5 Journal of Mathematical Sciences (New York)
5 Logical Methods in Computer Science
5 Journal of Logic and Analysis
4 Mathematical Social Sciences
4 Journal of Complexity
4 Journal of the American Mathematical Society
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 Approximate Reasoning
3 International Journal of Algebra and Computation
3 Computational Complexity
3 The Journal of Artificial Intelligence Research (JAIR)
3 Constraints
3 Acta Mathematica Sinica. English Series
3 Natural Computing
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 Annals of Operations Research
2 International Journal of Foundations of Computer Science
2 International Journal of Computer Mathematics
2 Stochastic Processes and their Applications
2 Mathematical Programming. Series A. Series B
2 New Zealand Journal of Mathematics
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 Sibirskie Èlektronnye Matematicheskie Izvestiya
2 Discrete Mathematics, Algorithms and Applications
2 RAIRO. Theoretical Informatics 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 Journal of Statistical Physics
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 Applied Mathematics and Computation
1 Computing
1 Fundamenta Mathematicae
1 Journal of Combinatorial Theory. Series A
1 Journal of Pure and Applied Algebra
...and 48 more Serials
all top 5

Cited in 40 Fields

1,306 Computer science (68-XX)
787 Mathematical logic and foundations (03-XX)
697 Combinatorics (05-XX)
191 Operations research, mathematical programming (90-XX)
90 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
57 Biology and other natural sciences (92-XX)
51 Order, lattices, ordered algebraic structures (06-XX)
29 Group theory and generalizations (20-XX)
21 Probability theory and stochastic processes (60-XX)
20 Information and communication theory, circuits (94-XX)
19 Measure and integration (28-XX)
15 General and overarching topics; collections (00-XX)
11 Dynamical systems and ergodic theory (37-XX)
10 History and biography (01-XX)
10 Number theory (11-XX)
10 Quantum theory (81-XX)
9 Statistics (62-XX)
9 Statistical mechanics, structure of matter (82-XX)
8 Real functions (26-XX)
8 General topology (54-XX)
8 Numerical analysis (65-XX)
6 Convex and discrete geometry (52-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 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 General algebraic systems (08-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.