![](https://dblp.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
default search action
Rodney G. Downey
Person information
- affiliation: Victoria University of Wellington, New Zealand
Refine list
![note](https://dblp.uni-trier.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
Books and Theses
- 2024
- [b4]Rod Downey:
Computability and Complexity - Foundations and Tools for Pursuing Scientific Applications. Undergraduate Topics in Computer Science, Springer 2024, ISBN 978-3-031-53743-1, pp. 3-326 - 2013
- [b3]Rodney G. Downey, Michael R. Fellows:
Fundamentals of Parameterized Complexity. Texts in Computer Science, Springer 2013, ISBN 978-1-4471-5558-4, pp. I-SSS, 3-707 - 2010
- [b2]Rodney G. Downey, Denis R. Hirschfeldt:
Algorithmic Randomness and Complexity. Theory and Applications of Computability, Springer 2010, ISBN 978-0-387-95567-4, pp. 1-766 - 1999
- [b1]Rodney G. Downey, Michael R. Fellows:
Parameterized Complexity. Monographs in Computer Science, Springer 1999, ISBN 978-1-4612-6798-0, pp. 1-437
Journal Articles
- 2024
- [j168]Klaus Ambos-Spies, Rod Downey, Martin Monath:
Lowness properties for strong reducibilities and the computational power of maximal sets. Comput. 13(1): 1-56 (2024) - 2023
- [j167]Rodney G. Downey
, Alexander G. Melnikov
:
Computably Compact Metric Spaces. Bull. Symb. Log. 29(2): 170-263 (2023) - [j166]Matthew Askes, Rod Downey:
Online, computable and punctual structure theory. Log. J. IGPL 31(6): 1251-1293 (2023) - 2022
- [j165]Rod Downey, Noam Greenberg, Matthew Harrison-Trainor, Ludovic Patey, Dan Turetsky:
Relationships between Computability-Theoretic Properties of Problems. J. Symb. Log. 87(1): 47-71 (2022) - [j164]Rod Downey, Matthew Harrison-Trainor:
A Minimal Set Low for Speed. J. Symb. Log. 87(4): 1693-1728 (2022) - 2021
- [j163]Katherine Arthur, Rod Downey, Noam Greenberg:
Maximality and collapse in the hierarchy of α-c.a. degrees. Comput. 10(3): 181-214 (2021) - [j162]Klaus Ambos-Spies, Rodney G. Downey, Martin Monath:
On Supersets of non-low 22_2 Sets. J. Symb. Log. 86(3): 1282-1292 (2021) - [j161]Rod Downey, Alexander G. Melnikov
, Keng Meng Ng:
Foundations of Online Structure Theory II: The Operator Approach. Log. Methods Comput. Sci. 17(3) (2021) - 2020
- [j160]Laurent Bienvenu, Rod Downey:
On low for speed oracles. J. Comput. Syst. Sci. 108: 49-63 (2020) - [j159]Rodney G. Downey, Matthew Harrison-Trainor, Iskander Sh. Kalimullin
, Alexander G. Melnikov
, Daniel Turetsky:
Graphs are not universal for online computability. J. Comput. Syst. Sci. 112: 1-12 (2020) - [j158]Rod Downey, Noam Greenberg, Alexander G. Melnikov
, Keng Meng Ng, Daniel Turetsky:
Punctual Categoricity and Universality. J. Symb. Log. 85(4): 1427-1466 (2020) - 2019
- [j157]Rod Downey, Alexander G. Melnikov
, Keng Meng Ng
:
Categorical linearly ordered structures. Ann. Pure Appl. Log. 170(10): 1243-1255 (2019) - [j156]Nikolay Bazhenov, Rod Downey, Iskander Sh. Kalimullin
, Alexander G. Melnikov
:
Foundations of Online Structure Theory. Bull. Symb. Log. 25(2): 141-181 (2019) - [j155]Rod Downey, Denis R. Hirschfeldt:
Algorithmic randomness. Commun. ACM 62(5): 70-80 (2019) - [j154]Vasco Brattka
, Rod Downey, Julia F. Knight, Steffen Lempp:
Preface of the special issue for the Oberwolfach Workshop on Computability Theory 2018. Comput. 8(3-4): 191 (2019) - [j153]Ellen Chih, Rod Downey:
Splitting theorems and low degrees. Comput. 8(3-4): 243-252 (2019) - [j152]Rodney G. Downey, Satyadev Nandakumar
:
A Weakly 2-Generic which Bounds a Minimal degree. J. Symb. Log. 84(4): 1326-1347 (2019) - [j151]Rodney G. Downey, Satyadev Nandakumar
, André Nies:
Martin-Löf Randomness Implies Multiple Recurrence in Effectively Closed Sets. Notre Dame J. Formal Log. 60(3): 491-502 (2019) - 2018
- [j150]Rod Downey, Keng Meng Ng
:
Splitting into degrees with low computational strength. Ann. Pure Appl. Log. 169(8): 803-834 (2018) - [j149]Rod Downey, Noam Greenberg:
A Hierarchy of computably Enumerable Degrees. Bull. Symb. Log. 24(1): 53-89 (2018) - [j148]Rodney G. Downey, Guohua Wu, Yue Yang:
Degrees containing members of thin Π10 classes are dense and co-dense. J. Math. Log. 18(1): 1850001:1-1850001:47 (2018) - [j147]Rod Downey, Jonathan Stephenson:
Avoiding Effective Packing Dimension 1 below array Noncomputable C.E. Degrees. J. Symb. Log. 83(2): 717-739 (2018) - [j146]Rod Downey, Denis R. Hirschfeldt, Bjørn Kjos-Hanssen:
Preface. Theory Comput. Syst. 62(7): 1553-1554 (2018) - 2017
- [j145]Benjamin A. Burton
, Rodney G. Downey:
Courcelle's theorem for triangulations. J. Comb. Theory A 146: 264-294 (2017) - [j144]Rodney G. Downey, Alexander G. Melnikov
, Keng Meng Ng
:
A Friedberg enumeration of equivalence structures. J. Math. Log. 17(2): 1750008:1-1750008:28 (2017) - [j143]Michelle Porter, Adam Day, Rodney G. Downey:
Notes on Computable Analysis. Theory Comput. Syst. 60(1): 53-111 (2017) - [j142]George Barmpalias
, Rodney G. Downey:
Kobayashi compressibility. Theor. Comput. Sci. 675: 89-100 (2017) - [j141]Rod Downey, Michael McInerney, Keng Meng Ng
:
Lowness and logical depth. Theor. Comput. Sci. 702: 23-33 (2017) - 2016
- [j140]Rodney G. Downey, Alexander G. Melnikov
, Keng Meng Ng
:
Abelian p-groups and the Halting problem. Ann. Pure Appl. Log. 167(11): 1123-1138 (2016) - 2015
- [j139]René van Bevern, Rodney G. Downey, Michael R. Fellows, Serge Gaspers, Frances A. Rosamond:
Myhill-Nerode Methods for Hypergraphs. Algorithmica 73(4): 696-729 (2015) - [j138]Rodney G. Downey, Guohua Wu, Yue Yang:
The members of thin and minimal classes, their ranks and Turing degrees. Ann. Pure Appl. Log. 166(7-8): 755-766 (2015) - [j137]Rod Downey, Alexander G. Melnikov
, Keng Meng Ng
:
On -categoricity of equivalence relations. Ann. Pure Appl. Log. 166(9): 851-880 (2015) - [j136]George Barmpalias
, Rodney G. Downey, Michael McInerney:
Integer valued betting strategies and Turing degrees. J. Comput. Syst. Sci. 81(7): 1387-1412 (2015) - [j135]Laurent Bienvenu, Rodney G. Downey, André Nies
, Wolfgang Merkle
:
Solovay functions and their applications in algorithmic randomness. J. Comput. Syst. Sci. 81(8): 1575-1591 (2015) - [j134]Rod Downey, Carl G. Jockusch Jr., Timothy H. McNicholl, Paul E. Schupp:
Asymptotic density and the Ershov hierarchy. Math. Log. Q. 61(3): 189-195 (2015) - 2014
- [j133]Mingzhong Cai, Rodney G. Downey, Rachel Epstein, Steffen Lempp, Joseph S. Miller
:
Random strings and tt-degrees of Turing complete C.E. sets. Log. Methods Comput. Sci. 10(3) (2014) - [j132]Rodney G. Downey, Alexander G. Melnikov
, Keng Meng Ng
:
Iterated effective embeddings of abelian p-groups. Int. J. Algebra Comput. 24(7): 1055- (2014) - [j131]Laurent Bienvenu, Rod Downey, Noam Greenberg, André Nies
, Daniel Turetsky:
Characterizing Lowness for Demuth Randomness. J. Symb. Log. 79(2): 526-560 (2014) - [j130]George Barmpalias
, Rodney G. Downey:
Exact Pairs for the Ideal of the k-Trivial Sequences in the Turing Degrees. J. Symb. Log. 79(3): 676-692 (2014) - 2013
- [j129]Rodney G. Downey, Carl G. Jockusch Jr., Paul E. Schupp:
Asymptotic density and computably Enumerable Sets. J. Math. Log. 13(2): 1350005 (2013) - [j128]Rod Downey:
Computability, Complexity and Randomness. Theory Comput. Syst. 52(1): 1 (2013) - 2012
- [j127]Rod Downey, Keng Meng Ng
:
Lowness for bounded randomness. Theor. Comput. Sci. 460: 1-9 (2012) - 2011
- [j126]Rodney G. Downey, Noam Greenberg, Carl G. Jockusch Jr., Kevin G. Milans:
Binary subtrees with few labeled paths. Comb. 31(3): 285-303 (2011) - [j125]Rodney G. Downey, Dimitrios M. Thilikos:
Confronting intractability via parameters. Comput. Sci. Rev. 5(4): 279-317 (2011) - [j124]George Barmpalias
, Rod Downey, Keng Meng Ng
:
Jump inversions inside effectively closed sets and applications to randomness. J. Symb. Log. 76(2): 491-518 (2011) - [j123]Barbara F. Csima, Rod Downey, Keng Meng Ng
:
Limits on jump inversion for strong reducibilities. J. Symb. Log. 76(4): 1287-1296 (2011) - [j122]Rodney G. Downey, Asher M. Kach:
Euclidean Functions of Computable Euclidean Domains. Notre Dame J. Formal Log. 52(2): 163-172 (2011) - 2010
- [j121]Rod Downey, Steffen Lempp, Guohua Wu:
On the Complexity of the Successivity Relation in Computable linear Orderings. J. Math. Log. 10(1-2) (2010) - [j120]Rodney G. Downey, Sergei S. Goncharov, Asher M. Kach, Julia F. Knight, Oleg V. Kudinov, Alexander G. Melnikov
, Daniel Turetsky:
Decidability and Computability of Certain Torsion-Free Abelian Groups. Notre Dame J. Formal Log. 51(1): 85-96 (2010) - [j119]Rod Downey, Keng Meng Ng
:
Effective Packing Dimension and Traceability. Notre Dame J. Formal Log. 51(2): 279-290 (2010) - 2009
- [j118]Douglas Cenzer, Rodney G. Downey, Jeffrey B. Remmel, Zia Uddin:
Space complexity of Abelian groups. Arch. Math. Log. 48(1): 115-140 (2009) - [j117]Hans L. Bodlaender
, Rodney G. Downey, Michael R. Fellows
, Danny Hermelin
:
On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8): 423-434 (2009) - [j116]Rodney G. Downey, Bart Kastermans, Steffen Lempp:
On computable self-embeddings of computable linear orderings. J. Symb. Log. 74(4): 1352-1366 (2009) - 2008
- [j115]Rod Downey, Noam Greenberg, Joseph S. Miller
:
The upward closure of a perfect thin class. Ann. Pure Appl. Log. 156(1): 51-58 (2008) - [j114]Peter Cholak, Rodney G. Downey, Leo Harrington:
The Complexity of Orbits of Computably Enumerable Sets. Bull. Symb. Log. 14(1): 69-87 (2008) - [j113]Rodney G. Downey, Michael R. Fellows
, Michael A. Langston:
The Computer Journal Special Issue on Parameterized Complexity: Foreword by the Guest Editors. Comput. J. 51(1): 1-6 (2008) - [j112]Rod Downey, Noam Greenberg:
Turing degrees of reals of positive effective packing dimension. Inf. Process. Lett. 108(5): 298-303 (2008) - [j111]Rodney G. Downey, Michael R. Fellows
, Catherine McCartin, Frances A. Rosamond
:
Parameterized approximation of dominating set problems. Inf. Process. Lett. 109(1): 68-70 (2008) - 2007
- [j110]Rod Downey, Jörg Flum, Martin Grohe
, Mark Weyer:
Bounded fixed-parameter tractability and reducibility. Ann. Pure Appl. Log. 148(1-3): 1-19 (2007) - [j109]Rodney G. Downey, Catherine McCartin:
Online promise problems with online width metrics. J. Comput. Syst. Sci. 73(1): 57-72 (2007) - [j108]Rodney G. Downey, Denis R. Hirschfeldt, Geoffrey LaForte:
Undecidability of the structure of the Solovay degrees of c.e. reals. J. Comput. Syst. Sci. 73(5): 769-787 (2007) - [j107]Rod Downey, Noam Greenberg, Rebecca Weber:
Totally ω-computably Enumerable Degrees and Bounding Critical Triples. J. Math. Log. 7(2) (2007) - [j106]Rod Downey:
Foreword. Theory Comput. Syst. 41(3): 397 (2007) - [j105]Rodney G. Downey, Jan Reimann
:
Algorithmic randomness. Scholarpedia 2(10): 2574 (2007) - 2006
- [j104]Rod Downey, Liang Yu:
Arithmetical Sacks Forcing. Arch. Math. Log. 45(6): 715-720 (2006) - [j103]Rodney G. Downey, Robert Goldblatt
:
Foreword. Ann. Pure Appl. Log. 138(1-3): 1- (2006) - [j102]Rodney G. Downey, Carl G. Jockusch Jr., Joseph S. Miller
:
On self-embeddings of computable linear orderings. Ann. Pure Appl. Log. 138(1-3): 52-76 (2006) - [j101]Rodney G. Downey, Denis R. Hirschfeldt, André Nies
, Sebastiaan Terwijn:
Calibrating Randomness. Bull. Symb. Log. 12(3): 411-491 (2006) - [j100]Rod Downey, André Nies
, Rebecca Weber, Liang Yu:
Lowness and Π20 nullsets. J. Symb. Log. 71(3): 1044-1052 (2006) - [j99]Barbara F. Csima, Rod Downey, Noam Greenberg, Denis R. Hirschfeldt, Joseph S. Miller
:
Every 1-generic computes a properly 1-generic. J. Symb. Log. 71(4): 1385-1393 (2006) - [j98]Rodney G. Downey, Wolfgang Merkle, Jan Reimann
:
Schnorr dimension. Math. Struct. Comput. Sci. 16(5): 789-811 (2006) - [j97]Rod Downey, Michael A. Langston, Rolf Niedermeier:
Editorial. Theor. Comput. Sci. 351(3): 295 (2006) - 2005
- [j96]Richard Coles, Rodney G. Downey, Carl G. Jockusch Jr., Geoffrey LaForte:
Completing pseudojump operators. Ann. Pure Appl. Log. 136(3): 297-333 (2005) - [j95]Rod Downey, Denis R. Hirschfeldt, Joseph S. Miller
, André Nies:
Relativizing Chaitin's Halting Probability. J. Math. Log. 5(2) (2005) - 2004
- [j94]Rod Downey, Angsheng Li, Guohua Wu:
Complementing cappable degrees in the difference hierarchy. Ann. Pure Appl. Log. 125(1-3): 101-118 (2004) - [j93]Liang Yu, Decheng Ding, Rodney G. Downey:
The Kolmogorov complexity of random reals. Ann. Pure Appl. Log. 129(1-3): 163-180 (2004) - [j92]Rodney G. Downey, Denis R. Hirschfeldt, Geoffrey LaForte:
Randomness and reducibility. J. Comput. Syst. Sci. 68(1): 96-114 (2004) - [j91]Rodney G. Downey, Evan J. Griffiths:
Schnorr randomness. J. Symb. Log. 69(2): 533-554 (2004) - [j90]Rod Downey, Guohua Wu, Xizhong Zheng:
Degrees of d. c. e. reals. Math. Log. Q. 50(4-5): 345-350 (2004) - [j89]Rod Downey, Evan J. Griffiths, Geoffrey LaForte:
On Schnorr and computable randomness, martingales, and machines. Math. Log. Q. 50(6): 613-627 (2004) - [j88]Rod Downey, Liang Yu:
There Are No Maximal Low D.C.E. Degrees. Notre Dame J. Formal Log. 45(3): 147-159 (2004) - [j87]Rodney G. Downey, Evan J. Griffiths, Stephanie Reid:
On Kurtz randomness. Theor. Comput. Sci. 321(2-3): 249-270 (2004) - 2003
- [j86]Rodney G. Downey, Geoffrey LaForte, Richard A. Shore:
Decomposition and infima in the computably enumerable degrees. J. Symb. Log. 68(2): 551-579 (2003) - [j85]Rodney G. Downey, Lance Fortnow:
Uniformly hard languages. Theor. Comput. Sci. 298(2): 303-315 (2003) - 2002
- [j84]Peter Cholak, Rodney G. Downey, Stephen Walk:
Maximal Contiguous Degrees. J. Symb. Log. 67(1): 409-437 (2002) - [j83]Rodney G. Downey, Steffen Lempp:
Contiguity and Distributivity in The Enumerable Turing Degrees - Corrigendum. J. Symb. Log. 67(4): 1579-1580 (2002) - [j82]Rodney G. Downey, Sebastiaan Terwijn:
Computably Enumerable Reals and Uniformly Presentable Ideals. Math. Log. Q. 48(S1): 29-40 (2002) - [j81]Rodney G. Downey:
Roman Murawski, Recursive Functions and Metamathematics. Stud Logica 70(2): 297-299 (2002) - [j80]Rodney G. Downey, Denis R. Hirschfeldt, André Nies
:
Randomness, Computability, and Density. SIAM J. Comput. 31(4): 1169-1183 (2002) - [j79]Rodney G. Downey, Geoffrey LaForte:
Presentations of computably enumerable reals. Theor. Comput. Sci. 284(2): 539-555 (2002) - 2001
- [j78]Rodney G. Downey, Michael R. Fellows
:
Index sets and parametric reductions. Arch. Math. Log. 40(5): 329-348 (2001) - [j77]Peter Cholak, Rodney G. Downey, Eberhard Herrmann:
Some orbits for E. Ann. Pure Appl. Log. 107(1-3): 193-226 (2001) - [j76]Rodney G. Downey, Denis R. Hirschfeldt, Steffen Lempp, Reed Solomon:
A delta02 Set with No Infinite Low Subset in Either It or Its Complement. J. Symb. Log. 66(3): 1371-1381 (2001) - [j75]Amy Gale, Rodney G. Downey:
On Genericity and Ershov's Hierarchy. Math. Log. Q. 47(2): 161-182 (2001) - 2000
- [j74]Rodney G. Downey, Michael R. Fellows, Venkatesh Raman:
The complexity of irredundant sets parameterized by size. Discret. Appl. Math. 100(3): 155-167 (2000) - [j73]Rodney G. Downey, André Nies
:
Undecidability Results for Low Complexity Time Classes. J. Comput. Syst. Sci. 60(2): 465-479 (2000) - [j72]Kevin Cattell, Michael J. Dinneen, Rodney G. Downey, Michael R. Fellows, Michael A. Langston:
On computing graph minor obstruction sets. Theor. Comput. Sci. 233(1-2): 107-127 (2000) - 1999
- [j71]Rodney G. Downey, Geoffrey LaForte, André Nies:
Addendum to "Computably Enumerable Sets and Quasi-Reducibility". Ann. Pure Appl. Log. 98(1-3): 295 (1999) - [j70]Rodney G. Downey, Michael R. Fellows, Ulrike Stege:
Computational Tractability: The View From Mars. Bull. EATCS 69: 73-97 (1999) - [j69]Rodney G. Downey, Carl G. Jockusch Jr.:
Effective Presentability of Boolean Algebras of Cantor-Bendixson Rank 1. J. Symb. Log. 64(1): 45-52 (1999) - [j68]Rodney G. Downey, Geoffrey LaForte, Steffen Lempp:
A Delta02 Set With Barely Sigma02 Degree. J. Symb. Log. 64(4): 1700-1718 (1999) - [j67]Rodney G. Downey, Michael R. Fellows, Alexander Vardy, Geoff Whittle:
The Parametrized Complexity of Some Fundamental Problems in Coding Theory. SIAM J. Comput. 29(2): 545-570 (1999) - 1998
- [j66]Rodney G. Downey, Zoltán Füredi, Carl G. Jockusch Jr., Lee A. Rubel:
Difference Sets and Computability Theory. Ann. Pure Appl. Log. 93(1-3): 63-72 (1998) - [j65]Rodney G. Downey, Richard A. Shore:
Splitting Theorems and the Jump Operator. Ann. Pure Appl. Log. 94(1-3): 45-52 (1998) - [j64]Rodney G. Downey, Geoffrey LaForte, André Nies
:
Computably Enumerable Sets and Quasi-Reducibility. Ann. Pure Appl. Log. 95(1-3): 1-35 (1998) - [j63]Rodney G. Downey, Michael R. Fellows, Kenneth W. Regan:
Parameterized Circuit Complexity and the W Hierarchy. Theor. Comput. Sci. 191(1-2): 97-115 (1998) - [j62]Rodney G. Downey, Michael R. Fellows:
Threshold Dominating Sets and an Improved Characterization of W[2]. Theor. Comput. Sci. 209(1-2): 123-140 (1998) - 1997
- [j61]Liming Cai, Jianer Chen, Rodney G. Downey, Michael R. Fellows:
On the parameterized complexity of short computation and factorization. Arch. Math. Log. 36(4-5): 321-337 (1997) - [j60]Liming Cai, Jianer Chen, Rodney G. Downey, Michael R. Fellows:
Advice Classes of Parameterized Tractability. Ann. Pure Appl. Log. 84(1): 119-138 (1997) - [j59]Rodney G. Downey, Steffen Lempp:
Contiguity and Distributivity in the Enumerable Turing Degrees. J. Symb. Log. 62(4): 1215-1240 (1997) - [j58]Bruno Courcelle, Rodney G. Downey, Michael R. Fellows:
A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second Order Ideals. J. Univers. Comput. Sci. 3(11): 1194-1198 (1997) - [j57]Rodney G. Downey:
On the Universal Splitting Property. Math. Log. Q. 43: 311-320 (1997) - [j56]Rich Blaylock, Rodney G. Downey, Steffen Lempp:
Infima in the Recursively Enumerable Weak Truth Table Degrees. Notre Dame J. Formal Log. 38(3): 406-418 (1997) - 1996
- [j55]Rodney G. Downey, Leo Harrington:
There is No Fat Orbit. Ann. Pure Appl. Log. 80(3): 277-289 (1996) - 1995
- [j54]Karl R. Abrahamson, Rodney G. Downey, Michael R. Fellows
:
Fixed-Parameter Tractability and Completeness IV: On Completeness for W[P] and PSPACE Analogues. Ann. Pure Appl. Log. 73(3): 235-276 (1995) - [j53]Hans L. Bodlaender
, Rodney G. Downey, Michael R. Fellows, Michael T. Hallett
, Harold T. Wareham:
Parameterized complexity analysis in computational biology. Comput. Appl. Biosci. 11(1): 49-57 (1995) - [j52]Liming Cai, Jianer Chen, Rodney G. Downey, Michael R. Fellows
:
On the Structure of Parameterized Problems in NP. Inf. Comput. 123(1): 38-49 (1995) - [j51]Rodney G. Downey, Richard A. Shore:
Degree Theoretic Definitions of the low2 Recursively Enumerable Sets. J. Symb. Log. 60(3): 727-756 (1995) - [j50]Rodney G. Downey, Michael R. Fellows:
Fixed-Parameter Tractability and Completeness I: Basic Results. SIAM J. Comput. 24(4): 873-921 (1995) - [j49]Rodney G. Downey, Michael R. Fellows
:
Fixed-Parameter Tractability and Completeness II: On Completeness for W[1]. Theor. Comput. Sci. 141(1&2): 109-131 (1995) - [j48]Hans L. Bodlaender
, Rodney G. Downey, Michael R. Fellows
, Harold T. Wareham:
The Parameterized Complexity of Sequence Alignment and Consensus. Theor. Comput. Sci. 147(1&2): 31-54 (1995) - 1994
- [j47]Rodney G. Downey, Steffen Lempp:
There is no plus-capping degree. Arch. Math. Log. 33(2): 109-119 (1994) - [j46]Rodney G. Downey, Yang Yue:
A Rank one Cohesive Set. Ann. Pure Appl. Log. 68(2): 161-171 (1994) - [j45]Rodney G. Downey, William I. Gasarch, Michael F. Moses:
The Structure of the Honest Polynomial m-Degrees. Ann. Pure Appl. Log. 70(2): 113-139 (1994) - [j44]Rodney G. Downey, Christine Ann Haught:
Embedding Lattices into the wtt-Degrees below 0'. J. Symb. Log. 59(4): 1360-1382 (1994) - 1993
- [j43]Douglas A. Cenzer, Rodney G. Downey, Carl G. Jockusch Jr., Richard A. Shore:
Countable Thin Pi01 Classes. Ann. Pure Appl. Log. 59(2): 79-139 (1993) - [j42]Rodney G. Downey, Michael Stob:
Friedberg Splittings of Recursively Enumerable Sets. Ann. Pure Appl. Log. 59(3): 175-199 (1993) - [j41]Rodney G. Downey:
Every Recursive Boolean Algebra is Isomorphic to One with Incomplete Atoms. Ann. Pure Appl. Log. 60(3): 193-206 (1993) - [j40]Peter Cholak, Rodney G. Downey:
Lattice Nonembeddings and Intervals of the Recursively Enumerable Degrees. Ann. Pure Appl. Log. 61(3): 195-221 (1993) - [j39]Rodney G. Downey, Michael Stob:
Splitting Theorems in Recursion Theory. Ann. Pure Appl. Logic 65(1): 1-106 (1993) - [j38]Peter Cholak, Rodney G. Downey:
On the Cantor-Bendixon Rank of Recursively Enumerable Sets. J. Symb. Log. 58(2): 629-640 (1993) - [j37]Steffen Lempp, Rodney G. Downey, Richard A. Shore:
Highness and Bounding Minimal Pairs. Math. Log. Q. 39: 475-491 (1993) - 1992
- [j36]Colin Bailey, Rodney G. Downey:
Tabular Degrees in alpha-Recursion Theory. Ann. Pure Appl. Log. 55(3): 205-236 (1992) - [j35]Rodney G. Downey, Theodore A. Slaman:
On co-Simple Isols and Their Intersection Types. Ann. Pure Appl. Log. 56(1-3): 221-237 (1992) - [j34]Rodney G. Downey:
Nondiamond Theorems for Polynomial Time Reducibility. J. Comput. Syst. Sci. 45(3): 385-395 (1992) - 1991
- [j33]Rod Downey, Mike Stob:
Jumps of Hemimaximal Sets. Math. Log. Q. 37(8): 113-120 (1991) - [j32]Rodney G. Downey:
On Π10 Classes and their Ranked Points. Notre Dame J. Formal Log. 32(4): 499-512 (1991) - [j31]Rodney G. Downey:
On Computational Complexity and Honest Polynomial Degrees. Theor. Comput. Sci. 78(2): 305-317 (1991) - 1990
- [j30]Chi Tat Chong, Rodney G. Downey:
Minimal Degrees Recursive in 1-Generic Degrees. Ann. Pure Appl. Log. 48(3): 215-225 (1990) - [j29]Rodney G. Downey:
Corrigendum: Correction to "Undecidability of L(Finfty) and Other Lattices of r.e. Substructures". Ann. Pure Appl. Log. 48(3): 299-301 (1990) - [j28]Rodney G. Downey:
Lattice Nonembeddings and Initial Segments of the Recursively Enumerable Degrees. Ann. Pure Appl. Log. 49(2): 97-119 (1990) - 1989
- [j27]Rodney G. Downey:
Intervals and Sublattices of the r.e. Weak Truth Table Degrees, Part I: Density. Ann. Pure Appl. Log. 41(1): 1-26 (1989) - [j26]Rodney G. Downey, Theodore A. Slaman:
Completely Mitotic r.e. Degrees. Ann. Pure Appl. Log. 41(2): 119-152 (1989) - [j25]Rodney G. Downey, Jeffrey B. Remmel:
Classification of Degree Classes Associated with r.e. Subspaces. Ann. Pure Appl. Log. 42(2): 105-124 (1989) - [j24]Rodney G. Downey:
Intervals and Sublattices of the r.e. Weak Truth Table Degrees, Part II: Nonbounding. Ann. Pure Appl. Log. 44(3): 153-172 (1989) - [j23]Rodney G. Downey:
Recursively Enumerable m- and tt-Degrees. I: The Quantity of m- Degrees. J. Symb. Log. 54(2): 553-567 (1989) - [j22]Rodney G. Downey:
On Hyper-Torre Isols. J. Symb. Log. 54(4): 1160-1166 (1989) - [j21]Rodney G. Downey, Michael F. Moses:
On Choice Sets and Strongly Non-Trivial Self-Embeddings of Recursive Linear Orders. Math. Log. Q. 35(3): 237-246 (1989) - [j20]Rod Downey:
A Contiguous Nonbranching Degree. Math. Log. Q. 35(4): 375-383 (1989) - 1988
- [j19]Rodney G. Downey:
Recursively enumerable m- and tt-degrees II: The distribution of singular degrees. Arch. Math. Log. 27(2): 135-147 (1988) - 1987
- [j18]Rodney G. Downey:
Localization of a theorem of Ambos-Spies and the strong anti-splitting property. Arch. Math. Log. 26(1): 127-136 (1987) - [j17]Rodney G. Downey:
Maximal theories. Ann. Pure Appl. Log. 33: 245-282 (1987) - [j16]Rodney G. Downey, Jeffrey B. Remmel:
Automorphisms and Recursive Structures. Math. Log. Q. 33(4): 339-345 (1987) - 1986
- [j15]Rodney G. Downey:
Sound, totally sound, and unsound recursive equivalence types. Ann. Pure Appl. Log. 31: 1-20 (1986) - [j14]Rodney G. Downey, Michael Stob:
Structural interactions of the recursively enumerable T- and W-degrees. Ann. Pure Appl. Log. 31: 205-236 (1986) - [j13]Rodney G. Downey:
Undecidability of L(F∞) and other lattices of r.e. substructures. Ann. Pure Appl. Log. 32: 17-26 (1986) - [j12]Rodney G. Downey, Stuart A. Kurtz:
Recursion theory and ordered groups. Ann. Pure Appl. Log. 32: 137-151 (1986) - [j11]Rodney G. Downey, Lawrence V. Welch:
Splitting Properties of R. E. Sets and Degrees. J. Symb. Log. 51(1): 88-109 (1986) - [j10]Rodney G. Downey:
Bases of Supermaximal Subspaces and Steinitz Systems II. Math. Log. Q. 32(13-16): 203-210 (1986) - 1985
- [j9]Rodney G. Downey, Geoffrey R. Hird:
Automorphisms of Supermaximal Subspaces. J. Symb. Log. 50(1): 1-9 (1985) - [j8]Rodney G. Downey, Iraj Kalantari:
Effective Extensions of Linear Forms on a Recursive Vector Space Over a Recursive Field. Math. Log. Q. 31(13): 193-200 (1985) - 1984
- [j7]Rodney G. Downey:
Co-Immune Subspaces and Complementation in V. J. Symb. Log. 49(2): 528-538 (1984) - [j6]Rodney G. Downey, Jeffrey B. Remmel:
The Universal Complementation Property. J. Symb. Log. 49(4): 1125-1136 (1984) - [j5]Christopher J. Ash, Rodney G. Downey:
Decidable Subspaces and Recursively Enumerable Subspaces. J. Symb. Log. 49(4): 1137-1145 (1984) - [j4]Rodney G. Downey:
Bases of Supermaximal Subspaces and Steinitz Systems. I. J. Symb. Log. 49(4): 1146-1159 (1984) - [j3]Rod Downey:
Some Remarks on a Theorem of Iraj Kalantari Concerning convexity and Recursion Theory. Math. Log. Q. 30(19-24): 295-302 (1984) - [j2]Rodney G. Downey:
A Note on Decompositions of Recursively Enumerable Subspaces. Math. Log. Q. 30(30): 465-470 (1984) - 1983
- [j1]Rod Downey:
On a Question of a. Retzlaff. Math. Log. Q. 29(6): 379-384 (1983)
Conference and Workshop Papers
- 2024
- [c38]Rod Downey, Noam Greenberg, Long Qian:
Some Open Questions and Recent Results on Computable Banach Spaces. CiE 2024: 10-26 - 2020
- [c37]Rodney G. Downey, Alexander G. Melnikov
:
Computable Analysis and Classification Problems. CiE 2020: 100-111 - 2018
- [c36]Laurent Bienvenu, Rodney G. Downey:
On Low for Speed Oracles. STACS 2018: 15:1-15:13 - 2012
- [c35]Rod Downey:
The Birth and Early Years of Parameterized Complexity. The Multivariate Algorithmic Revolution and Beyond 2012: 17-38 - [c34]Paul Brodhead, Rod Downey, Keng Meng Ng
:
Bounded Randomness. Computation, Physics and Beyond 2012: 59-70 - [c33]Rod Downey:
A Basic Parameterized Complexity Primer. The Multivariate Algorithmic Revolution and Beyond 2012: 91-128 - [c32]Rod Downey:
Randomness, Computation and Mathematics. CiE 2012: 162-181 - [c31]Rod Downey:
A Parameterized Complexity Tutorial. LATA 2012: 38-56 - 2009
- [c30]Rod Downey, Keng Meng Ng
:
Lowness for Demuth Randomness. CiE 2009: 154-166 - [c29]Laurent Bienvenu, Rod Downey:
Kolmogorov Complexity and Solovay Functions. STACS 2009: 147-158 - 2008
- [c28]Hans L. Bodlaender
, Rodney G. Downey, Michael R. Fellows
, Danny Hermelin
:
On Problems without Polynomial Kernels (Extended Abstract). ICALP (1) 2008: 563-574 - 2006
- [c27]Rodney G. Downey, Michael R. Fellows, Catherine McCartin:
Parameterized Approximation Problems. IWPEC 2006: 121-129 - [c26]Rod Downey, Noam Greenberg:
Totally < ωω Computably Enumerable and m-topped Degrees. TAMC 2006: 46-60 - 2005
- [c25]Rodney G. Downey, Catherine McCartin:
Bounded Persistence Pathwidth. CATS 2005: 51-56 - [c24]Rodney G. Downey, Wolfgang Merkle, Jan Reimann:
Schnorr Dimension. CiE 2005: 96-105 - 2004
- [c23]Rodney G. Downey, Catherine McCartin:
Some New Directions and Questions in Parameterized Complexity. Developments in Language Theory 2004: 12-26 - [c22]Rodney G. Downey, Catherine McCartin:
Online Problems, Pathwidth, and Persistence. IWPEC 2004: 13-24 - [c21]Rodney G. Downey:
Some Recent Progress in Algorithmic Randomness. MFCS 2004: 42-83 - 2003
- [c20]Rodney G. Downey, Vladimir Estivill-Castro
, Michael R. Fellows
, Elena Prieto-Rodriguez
, Frances A. Rosamond:
Cutting Up is Hard to Do: the Parameterized Complexity of k-Cut and Related Problems. CATS 2003: 209-222 - 2002
- [c19]Rodney G. Downey, Evan J. Griffiths:
Schnorr Randomness. CCA 2002: 25-35 - [c18]Rodney G. Downey, Denis R. Hirschfeldt, André Nies
, Frank Stephan
:
Trivial Reals. CCA 2002: 36-52 - 2001
- [c17]Rodney G. Downey, Denis R. Hirschfeldt, Geoffrey LaForte:
Randomness and Reducibility. MFCS 2001: 316-327 - [c16]Rodney G. Downey, Denis R. Hirschfeldt, André Nies:
Randomness, Computability, and Density. STACS 2001: 195-205 - 1998
- [c15]Rodney G. Downey, Lance Fortnow:
Uniformly Hard Languages. CCC 1998: 228- - 1997
- [c14]Rodney G. Downey, André Nies
:
Undecidability Results for Low Complexity Degree Structures. CCC 1997: 128-132 - [c13]Rodney G. Downey, Michael R. Fellows, Ulrike Stege:
Parameterized complexity: A framework for systematically confronting computational intractability. Contemporary Trends in Discrete Mathematics 1997: 49-99 - 1996
- [c12]Rodney G. Downey, Michael R. Fellows, Kenneth W. Regan:
Descriptive complexity and the W hierarchy. Proof Complexity and Feasible Arithmetics 1996: 119-134 - [c11]Rodney G. Downey, Michael R. Fellows, Udayan Taylor:
The Parameterized Complexity of Relational Database Queries and an Improved Characterization of W[1]. DMTCS 1996: 194-213 - 1995
- [c10]Peter Cholak, Rod Downey, Richard A. Shore:
Intervals Without Critical Triples. Logic Colloquium 1995: 17-43 - 1994
- [c9]Hans L. Bodlaender
, Rodney G. Downey, Michael R. Fellows, Harold T. Wareham:
The Parameterized Complexity of Sequence Alignment and Consensus. CPM 1994: 15-30 - [c8]Bruce M. Kapron
, Michael R. Fellows, Rodney G. Downey, Michael T. Hallett
, Harold T. Wareham:
The Parameterized Complexity of Some Problems in Logic and Linguistics. LFCS 1994: 89-100 - [c7]Liming Cai, Jianer Chen, Rodney G. Downey, Michael R. Fellows:
On the Structure of Parameterized Problems in NP (Extended Abstract). STACS 1994: 509-520 - 1993
- [c6]Rodney G. Downey, Patricia A. Evans, Michael R. Fellows:
Parameterized Learning Complexity. COLT 1993: 51-57 - [c5]Karl R. Abrahamson, Rodney G. Downey, Michael R. Fellows:
Fixed-Parameter Intractability II (Extended Abstract). STACS 1993: 374-385 - 1992
- [c4]Rodney G. Downey, Michael R. Fellows:
Fixed-Parameter Intractability. SCT 1992: 36-49 - [c3]Peter Cholak, Efim B. Kinber, Rodney G. Downey, Martin Kummer, Lance Fortnow, Stuart A. Kurtz, William I. Gasarch, Theodore A. Slaman:
Degrees of Inferability. COLT 1992: 180-192 - [c2]Rodney G. Downey, Michael R. Fellows:
Fixed Parameter Tractability and Completeness III: Some Structural Aspects of the W Hierarchy. Complexity Theory: Current Research 1992: 191-225 - 1989
- [c1]Rodney G. Downey, Steven Homer, William I. Gasarch, Michael F. Moses:
On Honest Polynomial Reductions, Relativizations, and P=NP. SCT 1989: 196-207
Parts in Books or Collections
- 2017
- [p2]Rod Downey:
Turing and randomness. The Turing Guide 2017: 427-436 - 2014
- [p1]Rod Downey:
Computability theory, algorithmic randomness and Turing's anticipation. Turing's Legacy 2014: 90-123
Editorship
- 2014
- [e6]Rod Downey:
Turing's Legacy: Developments from Turing's Ideas in Logic. Lecture Notes in Logic 42, Cambridge University Press 2014, ISBN 9781107338579 [contents] - 2012
- [e5]Hans L. Bodlaender
, Rod Downey, Fedor V. Fomin, Dániel Marx:
The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. Lecture Notes in Computer Science 7370, Springer 2012, ISBN 978-3-642-30890-1 [contents] - 2009
- [e4]Rod Downey, Prabhu Manyem:
Theory of Computing 2009, Fifteenth Computing: The Australasian Theory Symposium, CATS 2009, Wellington, New Zealand, January 2009. CRPIT 94, Australian Computer Society 2009, ISBN 978-1-920682-75-0 [contents] - 2008
- [e3]Rod Downey, Bakhadyr Khoussainov, Dietrich Kuske, Markus Lohrey, Moshe Y. Vardi:
Algorithmic-Logical Theory of Infinite Structures, 28.10. - 02.11.2007. Dagstuhl Seminar Proceedings 07441, Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany 2008 [contents] - 2006
- [e2]Rodney G. Downey, Martin Grohe, Gerhard J. Woeginger:
Exact Algorithms and Fixed-Parameter Tractability, 24.-27. July 2005. Dagstuhl Seminar Proceedings 05301, Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany 2006 [contents] - 2004
- [e1]Rodney G. Downey, Michael R. Fellows, Frank K. H. A. Dehne:
Parameterized and Exact Computation, First International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004, Proceedings. Lecture Notes in Computer Science 3162, Springer 2004, ISBN 3-540-23071-8 [contents]
Informal and Other Publications
- 2017
- [i14]Laurent Bienvenu, Rod Downey:
On low for speed oracles. CoRR abs/1712.09710 (2017) - [i13]Klaus Ambos-Spies, Vasco Brattka, Rodney G. Downey, Steffen Lempp:
Computability Theory (Dagstuhl Seminar 17081). Dagstuhl Reports 7(2): 89-101 (2017) - [i12]Yijia Chen, Rodney G. Downey, Jörg Flum:
Logic and Computational Complexity (NII Shonan Meeting 2017-13). NII Shonan Meet. Rep. 2017 (2017) - 2016
- [i11]George Barmpalias, Rodney G. Downey:
Kobayashi compressibility. CoRR abs/1608.00692 (2016) - 2015
- [i10]George Barmpalias, Rodney G. Downey, Michael McInerney:
Integer Valued Betting strategies and Turing Degrees. CoRR abs/1505.05298 (2015) - 2014
- [i9]Benjamin A. Burton, Rodney G. Downey:
Courcelle's theorem for triangulations. CoRR abs/1403.2926 (2014) - [i8]Rodney G. Downey, Kenshi Miyabe, André Nies, Osamu Watanabe:
Algorithmic Randomness and Complexity (NII Shonan Meeting 2014-10). NII Shonan Meet. Rep. 2014 (2014) - 2012
- [i7]Verónica Becher
, Laurent Bienvenu, Rodney G. Downey, Elvira Mayordomo
:
Computability, Complexity and Randomness (Dagstuhl Seminar 12021). Dagstuhl Reports 2(1): 19-38 (2012) - 2011
- [i6]Rodney G. Downey, Dimitrios M. Thilikos:
Confronting Intractability via Parameters. CoRR abs/1106.3161 (2011) - 2009
- [i5]Laurent Bienvenu, Rod Downey:
Kolmogorov Complexity and Solovay Functions. CoRR abs/0902.1041 (2009) - 2007
- [i4]Rod Downey, Bakhadyr Khoussainov, Dietrich Kuske, Markus Lohrey, Moshe Y. Vardi:
07441 Summary -- Algorithmic-Logical Theory of Infinite Structures. Algorithmic-Logical Theory of Infinite Structures 2007 - [i3]Rod Downey, Bakhadyr Khoussainov, Dietrich Kuske, Markus Lohrey, Moshe Y. Vardi:
07441 Abstracts Collection -- Algorithmic-Logical Theory of Infinite Structures. Algorithmic-Logical Theory of Infinite Structures 2007 - 2005
- [i2]Rodney G. Downey, Martin Grohe, Gerhard J. Woeginger:
05301 Summary - Exact Algorithms and Fixed-Parameter Tractability. Exact Algorithms and Fixed-Parameter Tractability 2005 - [i1]Rodney G. Downey, Martin Grohe, Gerhard J. Woeginger:
05301 Abstracts Collection - Exact Algorithms and Fixed-Parameter Tractability. Exact Algorithms and Fixed-Parameter Tractability 2005
Coauthor Index
![](https://dblp.uni-trier.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-10 01:24 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint