×

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,822 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

243 Publications have been cited 3,922 times in 2,332 Documents Cited by Year
Parameterized complexity. Zbl 0914.68076
Downey, R. G.; Fellows, M. R.
487
1998
Fundamentals of parameterized complexity. Zbl 1358.68006
Downey, Rodney G.; Fellows, Michael R.
471
2013
Algorithmic randomness and complexity. Zbl 1221.68005
Downey, Rodney G.; Hirschfeldt, Denis R.
359
2010
On problems without polynomial kernels. Zbl 1192.68288
Bodlaender, Hans L.; Downey, Rodney G.; Fellows, Michael R.; Hermelin, Danny
184
2009
Fixed-parameter tractability and completeness II: On completeness for W[1]. Zbl 0873.68059
Downey, Rod G.; Fellows, Michael R.
135
1995
Fixed-parameter tractability and completeness. I: Basic results. Zbl 0830.68063
Downey, Rod G.; Fellows, Michael R.
112
1995
Parameterized complexity after (almost) ten years: Review and open questions. Zbl 0961.68533
Downey, Rodney G.; Fellows, Michael R.
111
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.
54
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.
44
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
The isomorphism problem for torsion-free abelian groups is analytic complete. Zbl 1156.03042
Downey, Rod; Montalbán, Antonio
32
2008
Trivial reals. Zbl 1044.03027
Downey, Rod G.; Hirschfeldt, Denis R.; Nies, André; Stephan, Frank
31
2003
The parametrized complexity of some fundamental problems in coding theory. Zbl 0943.68079
Downey, Rod G.; Fellows, Michael R.; Vardy, Alexander; Whittle, Geoff
30
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.
28
1997
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.
28
2003
Array nonrecursive degrees and genericity. Zbl 0849.03029
Downey, Rod; Jockusch, Carl G.; Stob, Michael
27
1996
Relativizing Chaitin’s halting probability. Zbl 1093.03025
Downey, Rod; Hirschfeldt, Denis R.; Miller, Joseph S.; Nies, André
26
2005
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
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.
23
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
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
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
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
Splitting theorems in recursion theory. Zbl 0792.03028
Downey, Rod; Stob, Michael
17
1993
T-degrees, jump classes, and strong reducibilities. Zbl 0638.03039
Downey, R. G.; Jockusch, C. G. jun.
17
1987
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
17
1997
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
Foundations of online structure theory. Zbl 1477.03167
Bazhenov, Nikolay; Downey, Rod; Kalimullin, Iskander; Melnikov, Alexander
17
2019
Lowness and \(\Pi^0_2\) nullsets. Zbl 1112.03040
Downey, Rod; Nies, Andre; Weber, Rebecca; Yu, Liang
16
2006
Structural interactions of the recursively enumerable T- and W-degrees. Zbl 0604.03015
Downey, R. G.; Stob, M.
16
1986
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
On Schnorr and computable randomness, martingales, and machines. Zbl 1062.68064
Downey, Rod; Griffiths, Evan; Laforte, Geoffrey
15
2004
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
15
2007
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
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
Computable completely decomposable groups. Zbl 1341.03056
Downey, Rodney; Melnikov, Alexander G.
13
2014
Countable thin \(\Pi^0_1\) classes. Zbl 0909.03039
Cenzer, Douglas; Downey, Rodney; Jockusch, Carl; Shore, Richard A.
13
1993
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
Parameterized circuit complexity and the \(W\) hierarchy. Zbl 0896.68057
Downey, Rodney G.; Fellows, Michael R.; Regan, Kenneth W.
13
1998
Ideals in computable rings. Zbl 1127.03037
Downey, Rodney G.; Lempp, Steffen; Mileti, Joseph R.
13
2007
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
Minimal degrees recursive in 1-generic degrees. Zbl 0714.03037
Chong, C. T.; Downey, R. G.
12
1990
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
On choice sets and strongly non-trivial self-embeddings of recursive linear orders. Zbl 0654.03032
Downey, Rodney G.; Moses, Michael F.
12
1989
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
Orderings with \(\alpha\)th jump degree 0\(^{(\alpha)}\). Zbl 0748.03027
Downey, Rodney; Knight, Julia F.
11
1992
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
\(\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
On initial segments of computable linear orders. Zbl 0915.03040
Coles, Richard J.; Downey, Rod; Khoussainov, Bakhadyr
11
1998
On Kurtz randomness. Zbl 1070.68054
Downey, Rodney G.; Griffiths, Evan J.; Reid, Stephanie
11
2004
Splitting properties of r.e. sets and degrees. Zbl 0597.03025
Downey, R. G.; Welch, L. V.
11
1986
The degrees of r. e. sets without the universal splitting property. Zbl 0576.03028
Downey, R. G.
10
1985
Recursive linear orders with incomplete successivities. Zbl 0813.03028
Downey, Rodney G.; Moses, Michael F.
10
1991
Automorphisms of the lattice of recursively enumerable sets: Promptly simple sets. Zbl 0769.03024
Cholak, Peter; Downey, Rod; Stob, Michael
10
1992
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
Decidable subspaces and recursively enumerable subspaces. Zbl 0585.03016
Ash, C. J.; Downey, R. G.
10
1984
Computably enumerable sets and quasi-reducibility. Zbl 0930.03049
Downey, R.; LaForte, G.; Nies, A.
10
1998
The Kolmogorov complexity of random reals. Zbl 1065.03025
Yu, Liang; Ding, Decheng; Downey, Rodney
10
2004
Every set has a least jump enumeration. Zbl 1023.03036
Coles, Richard J.; Downey, Rod G.; Slaman, Theodore A.
10
2000
Automorphisms of supermaximal subspaces. Zbl 0572.03024
Downey, R. G.; Hird, G. R.
10
1985
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
On a question of A. Retzlaff. Zbl 0526.03028
Downey, Rod
9
1983
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
Strong jump-traceability. II: \(K\)-triviality. Zbl 1273.03141
Downey, Rod; Greenberg, Noam
9
2012
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
Questions in computable algebra and combinatorics. Zbl 0980.03045
Downey, Rod; Remmel, J. B.
8
2000
Computable algebras and closure systems: Coding properties. Zbl 0939.03046
Downey, R. G.; Remmel, J. B.
8
1998
Uniformity in computable structure theory. Zbl 1063.03018
Downey, Rod; Hirschfeldt, Denis; Khoussainov, Bakhadyr
8
2003
Abelian \(p\)-groups and the halting problem. Zbl 1402.03067
Downey, Rodney; Melnikov, Alexander G.; Ng, Keng Meng
8
2016
Friedberg splittings of recursively enumerable sets. Zbl 0795.03057
Downey, Rod; Stob, Michael
7
1993
Classification of degree classes associated with r.e. subspaces. Zbl 0628.03033
Downey, R. G.; Remmel, J. B.
7
1989
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 1485.03174
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
Computability and randomness. Zbl 1423.03145
Downey, Rod; Hirschfeldt, Denis R.
1
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
6
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
Degrees containing members of thin \(\Pi_1^0\) classes are dense and co-dense. Zbl 06887311
Downey, Rodney G.; Wu, Guohua; Yang, Yue
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.
5
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
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
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.
471
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.
359
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
184
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
32
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 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
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
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
15
2007
Ideals in computable rings. Zbl 1127.03037
Downey, Rodney G.; Lempp, Steffen; Mileti, Joseph R.
13
2007
Totally \(\omega\)-computably enumerable degrees and bounding critical triples. Zbl 1149.03032
Downey, Rod; Greenberg, Noam; Weber, Rebecca
13
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
Totally \(< \omega^{ \omega }\) computably enumerable and \(m\)-topped degrees. Zbl 1109.03039
Downey, Rod; Greenberg, Noam
2
2006
Schnorr dimension. Zbl 1125.03033
Downey, Rodney; Merkle, Wolfgang; Reimann, Jan
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
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
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
...and 143 more Documents
all top 5

Cited by 1,872 Authors

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

Cited in 155 Serials

316 Theoretical Computer Science
151 Annals of Pure and Applied Logic
141 Journal of Computer and System Sciences
141 Algorithmica
131 Discrete Applied Mathematics
131 The Journal of Symbolic Logic
76 Theory of Computing Systems
75 Information Processing Letters
59 Information and Computation
44 Journal of Discrete Algorithms
43 Archive for Mathematical Logic
40 The Bulletin of Symbolic Logic
38 SIAM Journal on Discrete Mathematics
34 Transactions of the American Mathematical Society
33 Proceedings of the American Mathematical Society
27 Notre Dame Journal of Formal Logic
27 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 Discrete Mathematics
11 Journal of Algebra
11 Operations Research Letters
11 Russian 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
8 Journal of Scheduling
7 Journal of Combinatorial Theory. Series B
7 European Journal of Combinatorics
7 MSCS. Mathematical Structures in Computer Science
7 Computer Science Review
6 Journal of Graph Algorithms and Applications
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 The Journal of Artificial Intelligence Research (JAIR)
5 Journal of Logic and Analysis
4 Mathematical Social Sciences
4 Journal of Complexity
4 International Journal of Approximate Reasoning
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 New Zealand Journal of Mathematics
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 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 Foundations of Physics
2 Oberwolfach Reports
2 Discrete Mathematics, Algorithms and Applications
2 Forum of Mathematics, Sigma
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
...and 55 more Serials
all top 5

Cited in 40 Fields

1,468 Computer science (68-XX)
844 Mathematical logic and foundations (03-XX)
765 Combinatorics (05-XX)
204 Operations research, mathematical programming (90-XX)
100 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
62 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)
20 Measure and integration (28-XX)
16 General and overarching topics; collections (00-XX)
12 Quantum theory (81-XX)
11 Number theory (11-XX)
11 Statistics (62-XX)
10 History and biography (01-XX)
10 Dynamical systems and ergodic theory (37-XX)
10 Statistical mechanics, structure of matter (82-XX)
9 Real functions (26-XX)
9 General topology (54-XX)
8 Convex and discrete geometry (52-XX)
7 Numerical analysis (65-XX)
6 Functional analysis (46-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)
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

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