Rodney G. Downey

Orcid: 0000-0003-4381-2845

Affiliations:
  • Victoria University of Wellington, New Zealand


According to our database1, Rodney G. Downey authored at least 214 papers between 1983 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Computability and Complexity - Foundations and Tools for Pursuing Scientific Applications
Undergraduate Topics in Computer Science, Springer, ISBN: 978-3-031-53743-1, 2024

ON THE C.E. DEGREES REALIZABLE IN $\Pi ^0_1$ CLASSES.
J. Symb. Log., 2024

Lowness properties for strong reducibilities and the computational power of maximal sets.
Comput., 2024

Some Open Questions and Recent Results on Computable Banach Spaces.
Proceedings of the Twenty Years of Theoretical and Practical Synergies, 2024

2023
Online, computable and punctual structure theory.
Log. J. IGPL, November, 2023

Computably Compact Metric Spaces.
Bull. Symb. Log., June, 2023

2022
A Minimal Set Low for Speed.
J. Symb. Log., December, 2022

Relationships between Computability-Theoretic Properties of Problems.
J. Symb. Log., 2022

2021
Foundations of Online Structure Theory II: The Operator Approach.
Log. Methods Comput. Sci., 2021

On Supersets of non-low 22_2 Sets.
J. Symb. Log., 2021

Maximality and collapse in the hierarchy of <i>α</i>-c.a. degrees.
Comput., 2021

2020
Punctual Categoricity and Universality.
J. Symb. Log., 2020

Graphs are not universal for online computability.
J. Comput. Syst. Sci., 2020

On low for speed oracles.
J. Comput. Syst. Sci., 2020

Computable Analysis and Classification Problems.
Proceedings of the Beyond the Horizon of Computability, 2020

2019
Martin-Löf Randomness Implies Multiple Recurrence in Effectively Closed Sets.
Notre Dame J. Formal Log., 2019

A Weakly 2-Generic which Bounds a Minimal degree.
J. Symb. Log., 2019

Splitting theorems and low degrees.
Comput., 2019

Preface of the special issue for the Oberwolfach Workshop on Computability Theory 2018.
Comput., 2019

Algorithmic randomness.
Commun. ACM, 2019

Foundations of Online Structure Theory.
Bull. Symb. Log., 2019

Categorical linearly ordered structures.
Ann. Pure Appl. Log., 2019

2018
Preface.
Theory Comput. Syst., 2018

Avoiding Effective Packing Dimension 1 below array Noncomputable C.E. Degrees.
J. Symb. Log., 2018

Degrees containing members of thin Π10 classes are dense and co-dense.
J. Math. Log., 2018

A Hierarchy of computably Enumerable Degrees.
Bull. Symb. Log., 2018

Splitting into degrees with low computational strength.
Ann. Pure Appl. Log., 2018

2017
Lowness and logical depth.
Theor. Comput. Sci., 2017

Kobayashi compressibility.
Theor. Comput. Sci., 2017

Logic and Computational Complexity (NII Shonan Meeting 2017-13).
NII Shonan Meet. Rep., 2017

Notes on Computable Analysis.
Theory Comput. Syst., 2017

A Friedberg enumeration of equivalence structures.
J. Math. Log., 2017

Courcelle's theorem for triangulations.
J. Comb. Theory A, 2017

Computability Theory (Dagstuhl Seminar 17081).
Dagstuhl Reports, 2017

Turing and randomness.
Proceedings of the Turing Guide., 2017

2016
Abelian p-groups and the Halting problem.
Ann. Pure Appl. Log., 2016

2015
Asymptotic density and the Ershov hierarchy.
Math. Log. Q., 2015

Solovay functions and their applications in algorithmic randomness.
J. Comput. Syst. Sci., 2015

Integer valued betting strategies and Turing degrees.
J. Comput. Syst. Sci., 2015

The members of thin and minimal classes, their ranks and Turing degrees.
Ann. Pure Appl. Log., 2015

On -categoricity of equivalence relations.
Ann. Pure Appl. Log., 2015

Myhill-Nerode Methods for Hypergraphs.
Algorithmica, 2015

2014
Algorithmic Randomness and Complexity (NII Shonan Meeting 2014-10).
NII Shonan Meet. Rep., 2014

Characterizing Lowness for Demuth Randomness.
J. Symb. Log., 2014

Exact Pairs for the Ideal of the <i>k</i>-Trivial Sequences in the Turing Degrees.
J. Symb. Log., 2014

Iterated effective embeddings of abelian p-groups.
Int. J. Algebra Comput., 2014

Random strings and tt-degrees of Turing complete C.E. sets.
Log. Methods Comput. Sci., 2014

Computability theory, algorithmic randomness and Turing's anticipation.
Proceedings of the Turing's Legacy: Developments from Turing's Ideas in Logic, 2014

2013
Fundamentals of Parameterized Complexity.
Texts in Computer Science, Springer, ISBN: 978-1-4471-5559-1, 2013

Computability, Complexity and Randomness.
Theory Comput. Syst., 2013

Asymptotic density and computably Enumerable Sets.
J. Math. Log., 2013

2012
Lowness for bounded randomness.
Theor. Comput. Sci., 2012

Computability, Complexity and Randomness (Dagstuhl Seminar 12021).
Dagstuhl Reports, 2012

A Parameterized Complexity Tutorial.
Proceedings of the Language and Automata Theory and Applications, 2012

Randomness, Computation and Mathematics.
Proceedings of the How the World Computes, 2012

A Basic Parameterized Complexity Primer.
Proceedings of the Multivariate Algorithmic Revolution and Beyond, 2012

The Birth and Early Years of Parameterized Complexity.
Proceedings of the Multivariate Algorithmic Revolution and Beyond, 2012

Bounded Randomness.
Proceedings of the Computation, Physics and Beyond, 2012

2011
Euclidean Functions of Computable Euclidean Domains.
Notre Dame J. Formal Log., 2011

Limits on jump inversion for strong reducibilities.
J. Symb. Log., 2011

Jump inversions inside effectively closed sets and applications to randomness.
J. Symb. Log., 2011

Confronting intractability via parameters.
Comput. Sci. Rev., 2011

Binary subtrees with few labeled paths.
Comb., 2011

2010
Effective Packing Dimension and Traceability.
Notre Dame J. Formal Log., 2010

Decidability and Computability of Certain Torsion-Free Abelian Groups.
Notre Dame J. Formal Log., 2010

On the Complexity of the Successivity Relation in Computable linear Orderings.
J. Math. Log., 2010

Algorithmic Randomness and Complexity.
Theory and Applications of Computability, Springer, ISBN: 978-0-387-95567-4, 2010

2009
On computable self-embeddings of computable linear orderings.
J. Symb. Log., 2009

On problems without polynomial kernels.
J. Comput. Syst. Sci., 2009

Space complexity of Abelian groups.
Arch. Math. Log., 2009

Kolmogorov Complexity and Solovay Functions.
Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

Lowness for Demuth Randomness.
Proceedings of the Mathematical Theory and Computational Practice, 2009

2008
Turing degrees of reals of positive effective packing dimension.
Inf. Process. Lett., 2008

Parameterized approximation of dominating set problems.
Inf. Process. Lett., 2008

The Computer Journal Special Issue on Parameterized Complexity: Foreword by the Guest Editors.
Comput. J., 2008

The Complexity of Orbits of Computably Enumerable Sets.
Bull. Symb. Log., 2008

The upward closure of a perfect thin class.
Ann. Pure Appl. Log., 2008

On Problems without Polynomial Kernels (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007
Algorithmic randomness.
Scholarpedia, 2007

Foreword.
Theory Comput. Syst., 2007

Totally ω-computably Enumerable Degrees and Bounding Critical Triples.
J. Math. Log., 2007

Online promise problems with online width metrics.
J. Comput. Syst. Sci., 2007

Undecidability of the structure of the Solovay degrees of c.e. reals.
J. Comput. Syst. Sci., 2007

Bounded fixed-parameter tractability and reducibility.
Ann. Pure Appl. Log., 2007

07441 Abstracts Collection -- Algorithmic-Logical Theory of Infinite Structures.
Proceedings of the Algorithmic-Logical Theory of Infinite Structures, 28.10. - 02.11.2007, 2007

07441 Summary -- Algorithmic-Logical Theory of Infinite Structures.
Proceedings of the Algorithmic-Logical Theory of Infinite Structures, 28.10. - 02.11.2007, 2007

2006
Editorial.
Theor. Comput. Sci., 2006

Schnorr dimension.
Math. Struct. Comput. Sci., 2006

Lowness and Π<sub>2</sub><sup>0</sup> nullsets.
J. Symb. Log., 2006

Every 1-generic computes a properly 1-generic.
J. Symb. Log., 2006

Calibrating Randomness.
Bull. Symb. Log., 2006

On self-embeddings of computable linear orderings.
Ann. Pure Appl. Log., 2006

Foreword.
Ann. Pure Appl. Log., 2006

Arithmetical Sacks Forcing.
Arch. Math. Log., 2006

Totally < ω<sup>ω</sup> Computably Enumerable and <i>m</i>-topped Degrees.
Proceedings of the Theory and Applications of Models of Computation, 2006

Parameterized Approximation Problems.
Proceedings of the Parameterized and Exact Computation, Second International Workshop, 2006

2005
Relativizing Chaitin's Halting Probability.
J. Math. Log., 2005

Completing pseudojump operators.
Ann. Pure Appl. Log., 2005

05301 Abstracts Collection - Exact Algorithms and Fixed-Parameter Tractability.
Proceedings of the Exact Algorithms and Fixed-Parameter Tractability, 24.-27. July 2005, 2005

05301 Summary - Exact Algorithms and Fixed-Parameter Tractability.
Proceedings of the Exact Algorithms and Fixed-Parameter Tractability, 24.-27. July 2005, 2005

Bounded Persistence Pathwidth.
Proceedings of the Theory of Computing 2005, 2005

2004
On Kurtz randomness.
Theor. Comput. Sci., 2004

There Are No Maximal Low D.C.E. Degrees.
Notre Dame J. Formal Log., 2004

Degrees of d. c. e. reals.
Math. Log. Q., 2004

On Schnorr and computable randomness, martingales, and machines.
Math. Log. Q., 2004

Schnorr randomness.
J. Symb. Log., 2004

Randomness and reducibility.
J. Comput. Syst. Sci., 2004

The Kolmogorov complexity of random reals.
Ann. Pure Appl. Log., 2004

Complementing cappable degrees in the difference hierarchy.
Ann. Pure Appl. Log., 2004

Some Recent Progress in Algorithmic Randomness.
Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

Online Problems, Pathwidth, and Persistence.
Proceedings of the Parameterized and Exact Computation, First International Workshop, 2004

Some New Directions and Questions in Parameterized Complexity.
Proceedings of the Developments in Language Theory, 2004

2003
Uniformly hard languages.
Theor. Comput. Sci., 2003

Decomposition and infima in the computably enumerable degrees.
J. Symb. Log., 2003

Cutting Up is Hard to Do: the Parameterized Complexity of k-Cut and Related Problems.
Proceedings of the Computing: the Australasian Theory Symposiumm, 2003

2002
Presentations of computably enumerable reals.
Theor. Comput. Sci., 2002

Randomness, Computability, and Density.
SIAM J. Comput., 2002

Roman Murawski, Recursive Functions and Metamathematics.
Stud Logica, 2002

Computably Enumerable Reals and Uniformly Presentable Ideals.
Math. Log. Q., 2002

Contiguity and Distributivity in The Enumerable Turing Degrees - Corrigendum.
J. Symb. Log., 2002

Maximal Contiguous Degrees.
J. Symb. Log., 2002

Trivial Reals.
Proceedings of the Computability and Complexity in Analysis, 2002

2001
On Genericity and Ershov's Hierarchy.
Math. Log. Q., 2001

A delta<sup>0</sup><sub>2</sub> Set with No Infinite Low Subset in Either It or Its Complement.
J. Symb. Log., 2001

Some orbits for E.
Ann. Pure Appl. Log., 2001

Index sets and parametric reductions.
Arch. Math. Log., 2001

2000
On computing graph minor obstruction sets.
Theor. Comput. Sci., 2000

Undecidability Results for Low Complexity Time Classes.
J. Comput. Syst. Sci., 2000

The complexity of irredundant sets parameterized by size.
Discret. Appl. Math., 2000

1999
Parameterized Complexity
Monographs in Computer Science, Springer, ISBN: 038794883X, 1999

The Parametrized Complexity of Some Fundamental Problems in Coding Theory.
SIAM J. Comput., 1999

A Delta<sup>0</sup><sub>2</sub> Set With Barely Sigma<sup>0</sup><sub>2</sub> Degree.
J. Symb. Log., 1999

Effective Presentability of Boolean Algebras of Cantor-Bendixson Rank 1.
J. Symb. Log., 1999

Computational Tractability: The View From Mars.
Bull. EATCS, 1999

Addendum to "Computably Enumerable Sets and Quasi-Reducibility".
Ann. Pure Appl. Log., 1999

1998
Parameterized Circuit Complexity and the W Hierarchy.
Theor. Comput. Sci., 1998

Threshold Dominating Sets and an Improved Characterization of <i>W</i>[2].
Theor. Comput. Sci., 1998

Splitting Theorems and the Jump Operator.
Ann. Pure Appl. Log., 1998

Computably Enumerable Sets and Quasi-Reducibility.
Ann. Pure Appl. Log., 1998

Difference Sets and Computability Theory.
Ann. Pure Appl. Log., 1998

1997
Infima in the Recursively Enumerable Weak Truth Table Degrees.
Notre Dame J. Formal Log., 1997

On the Universal Splitting Property.
Math. Log. Q., 1997

A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second Order Ideals.
J. Univers. Comput. Sci., 1997

Contiguity and Distributivity in the Enumerable Turing Degrees.
J. Symb. Log., 1997

Advice Classes of Parameterized Tractability.
Ann. Pure Appl. Log., 1997

On the parameterized complexity of short computation and factorization.
Arch. Math. Log., 1997

Parameterized complexity: A framework for systematically confronting computational intractability.
Proceedings of the Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, 1997

Undecidability Results for Low Complexity Degree Structures.
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996
There is No Fat Orbit.
Ann. Pure Appl. Log., 1996

The Parameterized Complexity of Relational Database Queries and an Improved Characterization of W[1].
Proceedings of the First Conference of the Centre for Discrete Mathematics and Theoretical Computer Science, 1996

Descriptive complexity and the <i>W</i> hierarchy.
Proceedings of the Proof Complexity and Feasible Arithmetics, 1996

1995
Fixed-Parameter Tractability and Completeness II: On Completeness for W[1].
Theor. Comput. Sci., 1995

The Parameterized Complexity of Sequence Alignment and Consensus.
Theor. Comput. Sci., 1995

Fixed-Parameter Tractability and Completeness I: Basic Results.
SIAM J. Comput., 1995

Degree Theoretic Definitions of the low<sub>2</sub> Recursively Enumerable Sets.
J. Symb. Log., 1995

On the Structure of Parameterized Problems in NP.
Inf. Comput., 1995

Parameterized complexity analysis in computational biology.
Comput. Appl. Biosci., 1995

Fixed-Parameter Tractability and Completeness IV: On Completeness for W[P] and PSPACE Analogues.
Ann. Pure Appl. Log., 1995

Intervals Without Critical Triples.
Proceedings of the Annual European Summer Meeting of the Association of Symbolic Logic, 1995

1994
Embedding Lattices into the wtt-Degrees below 0'.
J. Symb. Log., 1994

A Rank one Cohesive Set.
Ann. Pure Appl. Log., 1994

The Structure of the Honest Polynomial m-Degrees.
Ann. Pure Appl. Log., 1994

There is no plus-capping degree.
Arch. Math. Log., 1994

On the Structure of Parameterized Problems in NP (Extended Abstract).
Proceedings of the STACS 94, 1994

The Parameterized Complexity of Some Problems in Logic and Linguistics.
Proceedings of the Logical Foundations of Computer Science, Third International Symposium, 1994

1993
Highness and Bounding Minimal Pairs.
Math. Log. Q., 1993

On the Cantor-Bendixon Rank of Recursively Enumerable Sets.
J. Symb. Log., 1993

Friedberg Splittings of Recursively Enumerable Sets.
Ann. Pure Appl. Log., 1993

Splitting Theorems in Recursion Theory.
Ann. Pure Appl. Logic, 1993

Every Recursive Boolean Algebra is Isomorphic to One with Incomplete Atoms.
Ann. Pure Appl. Log., 1993

Lattice Nonembeddings and Intervals of the Recursively Enumerable Degrees.
Ann. Pure Appl. Log., 1993

Countable Thin Pi<sup>0</sup><sub>1</sub> Classes.
Ann. Pure Appl. Log., 1993

Fixed-Parameter Intractability II (Extended Abstract).
Proceedings of the STACS 93, 1993

Parameterized Learning Complexity.
Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, 1993

1992
Nondiamond Theorems for Polynomial Time Reducibility.
J. Comput. Syst. Sci., 1992

On co-Simple Isols and Their Intersection Types.
Ann. Pure Appl. Log., 1992

Tabular Degrees in alpha-Recursion Theory.
Ann. Pure Appl. Log., 1992

Fixed Parameter Tractability and Completeness III: Some Structural Aspects of the W Hierarchy.
Proceedings of the Complexity Theory: Current Research, 1992

Degrees of Inferability.
Proceedings of the Fifth Annual ACM Conference on Computational Learning Theory, 1992

Fixed-Parameter Intractability.
Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1991
On Computational Complexity and Honest Polynomial Degrees.
Theor. Comput. Sci., 1991

On Π<sub>1</sub><sup>0</sup> Classes and their Ranked Points.
Notre Dame J. Formal Log., 1991

Jumps of Hemimaximal Sets.
Math. Log. Q., 1991

1990
Lattice Nonembeddings and Initial Segments of the Recursively Enumerable Degrees.
Ann. Pure Appl. Log., 1990

Corrigendum: Correction to "Undecidability of L(F<sub>infty</sub>) and Other Lattices of r.e. Substructures".
Ann. Pure Appl. Log., 1990

Minimal Degrees Recursive in 1-Generic Degrees.
Ann. Pure Appl. Log., 1990

1989
On Choice Sets and Strongly Non-Trivial Self-Embeddings of Recursive Linear Orders.
Math. Log. Q., 1989

A Contiguous Nonbranching Degree.
Math. Log. Q., 1989

On Hyper-Torre Isols.
J. Symb. Log., 1989

Recursively Enumerable m- and tt-Degrees. I: The Quantity of m- Degrees.
J. Symb. Log., 1989

Completely Mitotic r.e. Degrees.
Ann. Pure Appl. Log., 1989

Classification of Degree Classes Associated with r.e. Subspaces.
Ann. Pure Appl. Log., 1989

Intervals and Sublattices of the r.e. Weak Truth Table Degrees, Part II: Nonbounding.
Ann. Pure Appl. Log., 1989

Intervals and Sublattices of the r.e. Weak Truth Table Degrees, Part I: Density.
Ann. Pure Appl. Log., 1989

On Honest Polynomial Reductions, Relativizations, and P=NP.
Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988
Recursively enumerable <i>m</i>- and <i>tt</i>-degrees II: The distribution of singular degrees.
Arch. Math. Log., 1988

1987
Automorphisms and Recursive Structures.
Math. Log. Q., 1987

Maximal theories.
Ann. Pure Appl. Log., 1987

Localization of a theorem of Ambos-Spies and the strong anti-splitting property.
Arch. Math. Log., 1987

1986
Bases of Supermaximal Subspaces and Steinitz Systems II.
Math. Log. Q., 1986

Splitting Properties of R. E. Sets and Degrees.
J. Symb. Log., 1986

Structural interactions of the recursively enumerable T- and W-degrees.
Ann. Pure Appl. Log., 1986

Recursion theory and ordered groups.
Ann. Pure Appl. Log., 1986

Sound, totally sound, and unsound recursive equivalence types.
Ann. Pure Appl. Log., 1986

Undecidability of L(F<sub>∞</sub>) and other lattices of r.e. substructures.
Ann. Pure Appl. Log., 1986

1985
Effective Extensions of Linear Forms on a Recursive Vector Space Over a Recursive Field.
Math. Log. Q., 1985

Automorphisms of Supermaximal Subspaces.
J. Symb. Log., 1985

1984
A Note on Decompositions of Recursively Enumerable Subspaces.
Math. Log. Q., 1984

Some Remarks on a Theorem of Iraj Kalantari Concerning convexity and Recursion Theory.
Math. Log. Q., 1984

The Universal Complementation Property.
J. Symb. Log., 1984

Bases of Supermaximal Subspaces and Steinitz Systems. I.
J. Symb. Log., 1984

Co-Immune Subspaces and Complementation in V.
J. Symb. Log., 1984

Decidable Subspaces and Recursively Enumerable Subspaces.
J. Symb. Log., 1984

1983
On a Question of a. Retzlaff.
Math. Log. Q., 1983


  Loading...