Rodney G. Downey

ORCID

Publication Activity (10 Years)

Years Active: 1984-2023
Publications (10 Years): 16

Top Venues

J. Comput. Syst. Sci.

CoRR

J. Symb. Log.

Ann. Pure Appl. Log.

Publications

Rodney G. Downey, Alexander G. Melnikov
Computably Compact Metric Spaces. Bull. Symb. Log. 29 (2) (2023)
Klaus Ambos-Spies, Rodney G. Downey, Martin Monath
On Supersets of non-low 22_2 Sets. J. Symb. Log. 86 (3) (2021)
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 (2020)
Rodney G. Downey, Alexander G. Melnikov
Computable Analysis and Classification Problems. CiE (2020)
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) (2019)
Rodney G. Downey, Satyadev Nandakumar
A Weakly 2-Generic which Bounds a Minimal degree. J. Symb. Log. 84 (4) (2019)
Rodney G. Downey, Guohua Wu, Yue Yang
Degrees containing members of thin Π10 classes are dense and co-dense. J. Math. Log. 18 (1) (2018)
Laurent Bienvenu, Rodney G. Downey
On Low for Speed Oracles. STACS (2018)
Klaus Ambos-Spies, Vasco Brattka, Rodney G. Downey, Steffen Lempp
Computability Theory (Dagstuhl Seminar 17081). Dagstuhl Reports 7 (2) (2017)
Benjamin A. Burton, Rodney G. Downey
Courcelle's theorem for triangulations. J. Comb. Theory, Ser. A 146 (2017)
George Barmpalias, Rodney G. Downey
Kobayashi compressibility. Theor. Comput. Sci. 675 (2017)
Michelle Porter, Adam Day, Rodney G. Downey
Notes on Computable Analysis. Theory Comput. Syst. 60 (1) (2017)
Rodney G. Downey, Alexander G. Melnikov, Keng Meng Ng
A Friedberg enumeration of equivalence structures. J. Math. Log. 17 (2) (2017)
Yijia Chen, Rodney G. Downey, Jörg Flum
Logic and Computational Complexity (NII Shonan Meeting 2017-13). NII Shonan Meet. Rep. 2017 (2017)
George Barmpalias, Rodney G. Downey
Kobayashi compressibility. CoRR (2016)
Rodney G. Downey, Alexander G. Melnikov, Keng Meng Ng
Abelian p-groups and the Halting problem. Ann. Pure Appl. Log. 167 (11) (2016)
George Barmpalias, Rodney G. Downey, Michael McInerney
Integer Valued Betting strategies and Turing Degrees. CoRR (2015)
George Barmpalias, Rodney G. Downey, Michael McInerney
Integer valued betting strategies and Turing degrees. J. Comput. Syst. Sci. 81 (7) (2015)
René van Bevern, Rodney G. Downey, Michael R. Fellows, Serge Gaspers, Frances A. Rosamond
Myhill-Nerode Methods for Hypergraphs. Algorithmica 73 (4) (2015)
Laurent Bienvenu, Rodney G. Downey, André Nies, Wolfgang Merkle
Solovay functions and their applications in algorithmic randomness. J. Comput. Syst. Sci. 81 (8) (2015)
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) (2015)
Rodney G. Downey, Alexander G. Melnikov, Keng Meng Ng
Iterated effective embeddings of abelian p-groups. Int. J. Algebra Comput. 24 (7) (2014)
Rodney G. Downey, Kenshi Miyabe, André Nies, Osamu Watanabe
Algorithmic Randomness and Complexity (NII Shonan Meeting 2014-10). NII Shonan Meet. Rep. 2014 (2014)
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)
George Barmpalias, Rodney G. Downey
-Trivial Sequences in the Turing Degrees. J. Symb. Log. 79 (3) (2014)
Benjamin A. Burton, Rodney G. Downey
Courcelle's theorem for triangulations. CoRR (2014)
Rodney G. Downey, Carl G. Jockusch Jr., Paul E. Schupp
Asymptotic density and computably Enumerable Sets. J. Math. Log. 13 (2) (2013)
Verónica Becher, Laurent Bienvenu, Rodney G. Downey, Elvira Mayordomo
Computability, Complexity and Randomness (Dagstuhl Seminar 12021). Dagstuhl Reports 2 (1) (2012)
Rodney G. Downey, Noam Greenberg, Carl G. Jockusch Jr., Kevin G. Milans
Binary subtrees with few labeled paths. Comb. 31 (3) (2011)
Rodney G. Downey, Dimitrios M. Thilikos
Confronting Intractability via Parameters CoRR (2011)
Rodney G. Downey, Dimitrios M. Thilikos
Confronting intractability via parameters. Comput. Sci. Rev. 5 (4) (2011)
Rodney G. Downey, Asher M. Kach
Euclidean Functions of Computable Euclidean Domains. Notre Dame J. Formal Log. 52 (2) (2011)
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) (2010)
Douglas Cenzer, Rodney G. Downey, Jeffrey B. Remmel, Zia Uddin
Space complexity of Abelian groups. Arch. Math. Log. 48 (1) (2009)
Rodney G. Downey, Bart Kastermans, Steffen Lempp
On computable self-embeddings of computable linear orderings. J. Symb. Log. 74 (4) (2009)
Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin
On problems without polynomial kernels. J. Comput. Syst. Sci. 75 (8) (2009)
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) (2008)
Peter Cholak, Rodney G. Downey, Leo Harrington
The Complexity of Orbits of Computably Enumerable Sets. Bull. Symb. Log. 14 (1) (2008)
Rodney G. Downey, Michael R. Fellows, Catherine McCartin, Frances A. Rosamond
Parameterized approximation of dominating set problems. Inf. Process. Lett. 109 (1) (2008)
Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin
On Problems without Polynomial Kernels (Extended Abstract). ICALP (1) (2008)
Rodney G. Downey, Jan Reimann
Algorithmic randomness. Scholarpedia 2 (10) (2007)
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) (2007)
Rodney G. Downey, Catherine McCartin
Online promise problems with online width metrics. J. Comput. Syst. Sci. 73 (1) (2007)
Rodney G. Downey, Michael R. Fellows, Catherine McCartin
Parameterized Approximation Problems. IWPEC (2006)
Rodney G. Downey, Denis R. Hirschfeldt, André Nies, Sebastiaan Terwijn
Calibrating Randomness. Bull. Symb. Log. 12 (3) (2006)
Rodney G. Downey, Carl G. Jockusch Jr., Joseph S. Miller
On self-embeddings of computable linear orderings. Ann. Pure Appl. Log. 138 (1-3) (2006)
Rodney G. Downey, Robert Goldblatt
Foreword. Ann. Pure Appl. Log. 138 (1-3) (2006)
Rodney G. Downey, Wolfgang Merkle, Jan Reimann
Schnorr dimension. Math. Struct. Comput. Sci. 16 (5) (2006)
Rodney G. Downey, Catherine McCartin
Bounded Persistence Pathwidth. CATS (2005)
Rodney G. Downey, Martin Grohe, Gerhard J. Woeginger
05301 Summary - Exact Algorithms and Fixed-Parameter Tractability. Exact Algorithms and Fixed-Parameter Tractability (2005)
Rodney G. Downey, Martin Grohe, Gerhard J. Woeginger
05301 Abstracts Collection - Exact Algorithms and Fixed-Parameter Tractability. Exact Algorithms and Fixed-Parameter Tractability (2005)
Richard Coles, Rodney G. Downey, Carl G. Jockusch Jr., Geoffrey LaForte
Completing pseudojump operators. Ann. Pure Appl. Log. 136 (3) (2005)
Rodney G. Downey, Wolfgang Merkle, Jan Reimann
Schnorr Dimension. CiE (2005)
Rodney G. Downey, Evan J. Griffiths, Stephanie Reid
On Kurtz randomness. Theor. Comput. Sci. 321 (2-3) (2004)
Rodney G. Downey, Catherine McCartin
Online Problems, Pathwidth, and Persistence. IWPEC (2004)
Rodney G. Downey, Denis R. Hirschfeldt, Geoffrey LaForte
Randomness and reducibility. J. Comput. Syst. Sci. 68 (1) (2004)
Rodney G. Downey
Some Recent Progress in Algorithmic Randomness. MFCS (2004)
Rodney G. Downey, Evan J. Griffiths
Schnorr randomness. J. Symb. Log. 69 (2) (2004)
Rodney G. Downey, Catherine McCartin
Some New Directions and Questions in Parameterized Complexity. Developments in Language Theory (2004)
Liang Yu, Decheng Ding, Rodney G. Downey
The Kolmogorov complexity of random reals. Ann. Pure Appl. Log. 129 (1-3) (2004)
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. Electron. Notes Theor. Comput. Sci. 78 (2003)
Rodney G. Downey, Lance Fortnow
Uniformly hard languages. Theor. Comput. Sci. 298 (2) (2003)
Rodney G. Downey, Geoffrey LaForte, Richard A. Shore
Decomposition and infima in the computably enumerable degrees. J. Symb. Log. 68 (2) (2003)
Peter Cholak, Rodney G. Downey, Stephen Walk
Maximal Contiguous Degrees. J. Symb. Log. 67 (1) (2002)
Rodney G. Downey, Denis R. Hirschfeldt, André Nies, Frank Stephan
Trivial Reals. Electron. Notes Theor. Comput. Sci. 66 (1) (2002)
Rodney G. Downey
Roman Murawski, Recursive Functions and Metamathematics. Stud Logica 70 (2) (2002)
Rodney G. Downey, Steffen Lempp
Contiguity and Distributivity in The Enumerable Turing Degrees - Corrigendum. J. Symb. Log. 67 (4) (2002)
Rodney G. Downey, Denis R. Hirschfeldt, André Nies
Randomness, Computability, and Density. SIAM J. Comput. 31 (4) (2002)
Rodney G. Downey, Sebastiaan Terwijn
Computably Enumerable Reals and Uniformly Presentable Ideals. Math. Log. Q. 48 (S1) (2002)
Rodney G. Downey, Evan J. Griffiths
Schnorr Randomness. Electron. Notes Theor. Comput. Sci. 66 (1) (2002)
Rodney G. Downey, Geoffrey LaForte
Presentations of computably enumerable reals. Theor. Comput. Sci. 284 (2) (2002)
Rodney G. Downey, Michael R. Fellows
Index sets and parametric reductions. Arch. Math. Log. 40 (5) (2001)
Rodney G. Downey, Denis R. Hirschfeldt, Geoffrey LaForte
Randomness and Reducibility. MFCS (2001)
Peter Cholak, Rodney G. Downey, Eberhard Herrmann
Some orbits for E. Ann. Pure Appl. Log. 107 (1-3) (2001)
Rodney G. Downey, Denis R. Hirschfeldt, André Nies
Randomness, Computability, and Density. STACS (2001)
Amy Gale, Rodney G. Downey
On Genericity and Ershov's Hierarchy. Math. Log. Q. 47 (2) (2001)
Rodney G. Downey, Denis R. Hirschfeldt, Steffen Lempp, Reed Solomon
Set with No Infinite Low Subset in Either It or Its Complement. J. Symb. Log. 66 (3) (2001)
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) (2000)
Rodney G. Downey, Michael R. Fellows, Venkatesh Raman
The complexity of irredundant sets parameterized by size. Discret. Appl. Math. 100 (3) (2000)
Rodney G. Downey, André Nies
Undecidability Results for Low Complexity Time Classes. J. Comput. Syst. Sci. 60 (2) (2000)
Rodney G. Downey, Geoffrey LaForte, André Nies
Addendum to "Computably Enumerable Sets and Quasi-Reducibility". Ann. Pure Appl. Log. 98 (1-3) (1999)
Rodney G. Downey, Carl G. Jockusch Jr.
Effective Presentability of Boolean Algebras of Cantor-Bendixson Rank 1. J. Symb. Log. 64 (1) (1999)
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) (1999)
Rodney G. Downey, Michael R. Fellows, Ulrike Stege
Computational Tractability: The View From Mars. Bull. EATCS 69 (1999)
Rodney G. Downey, Geoffrey LaForte, Steffen Lempp
Degree. J. Symb. Log. 64 (4) (1999)
Rodney G. Downey, Michael R. Fellows
[2]. Theor. Comput. Sci. 209 (1-2) (1998)
Rodney G. Downey, Lance Fortnow
Uniformly Hard Languages. Computational Complexity Conference (1998)
Rodney G. Downey, Geoffrey LaForte, André Nies
Computably Enumerable Sets and Quasi-Reducibility. Ann. Pure Appl. Log. 95 (1-3) (1998)
Rodney G. Downey, Richard A. Shore
Splitting Theorems and the Jump Operator. Ann. Pure Appl. Log. 94 (1-3) (1998)
Rodney G. Downey, Michael R. Fellows, Kenneth W. Regan
Parameterized Circuit Complexity and the W Hierarchy. Theor. Comput. Sci. 191 (1-2) (1998)
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) (1998)
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) (1997)
Rodney G. Downey, Steffen Lempp
Contiguity and Distributivity in the Enumerable Turing Degrees. J. Symb. Log. 62 (4) (1997)
Rodney G. Downey, Michael R. Fellows, Ulrike Stege
Parameterized complexity: A framework for systematically confronting computational intractability. Contemporary Trends in Discrete Mathematics (1997)
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) (1997)
Rodney G. Downey
On the Universal Splitting Property. Math. Log. Q. 43 (1997)
Rich Blaylock, Rodney G. Downey, Steffen Lempp
Infima in the Recursively Enumerable Weak Truth Table Degrees. Notre Dame J. Formal Log. 38 (3) (1997)
Rodney G. Downey, André Nies
Undecidability Results for Low Complexity Degree Structures. Computational Complexity Conference (1997)
Liming Cai, Jianer Chen, Rodney G. Downey, Michael R. Fellows
Advice Classes of Parameterized Tractability. Ann. Pure Appl. Log. 84 (1) (1997)
Rodney G. Downey, Michael R. Fellows, Udayan Taylor
The Parameterized Complexity of Relational Database Queries and an Improved Characterization of W[1]. DMTCS (1996)

Rodney G. Downey.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Rodney G. Downey