Rod Downey's Publications for Download
Degree Theory
Randomness
Parameterized Complexity
Computable Model Theory
Effective Algebra, Analysis, and Computable Combinatorics
Lattice of Computably Enumerable Sets
Reverse Mathematics
Complexity Theory Miscellaneous
Computability Miscellaneous
Miscellaneous
Intervals and sublattices of the r.e. weak truth table degrees
part 1: density
Intervals and sublattices of the r.e. weak truth table degrees
part 2: nonbounding
Highness and bounding minimal pairs (With Lempp and Shore)
Infima in the Recursively Enumerable Weak Truth Table Degrees (With Blaylock and Lempp
)
Jumps of Minimal Degrees Below 0' (With Lempp and Shore)
Array Nonrecursive Sets and Multiple Permitting Arguments (With Jockusch and Stob)
A Delta 2 set that is barely Sigma 2 (With LaForte and Lempp)
$\Delta_2^0$ Degrees and Transfer Theorems
Array nonrecursive degrees and lattice embeddings of the
diamond
T-degrees, jump classes and strong reducibilties
(with Jockusch)
On Pi-0-1 Classes and their Ranked Points
Some Notes on the wtt-Jump(with Ambos-Spies and Monath)
On Supersets of Non-Low$_2$ Sets(with Ambos-Spies a
nd Monath)
Minimal Degrees Recursive in 1-Generic Degrees (With Chong)
Degrees Bounding Minimal Degrees (With Chong
)
Notes on the 0``` Priority Method with Special Attention to Density Arguments )
Lattice Nonembeddings and Initial Segments of the Recursively Enumerable
Degrees
Minimal pairs in initial segments of the recursively
enumerable degrees (with M. Stob)
Superbranching
Degrees (with Mourad)
Recursively Enumerable m- and tt-degrees I: The Quantity of m-degrees
Recursively Enumerable m- and tt-degrees II: The Distribution of Singular Degrees
Recursively Enumerable m- and tt-degrees III: Realizing all finite distributive lattices (with Cholak)
Computably Enumerable Sets and Quasi-reducibility (With LaForte and Nies)
Array Nonrecursive Degrees and Genericity (With Jockusch and Stob)
Contiguity and Distributivity in the Enumerable Turing Degrees (With Lempp)
Contiguity and Distributivity in the Enumerable Turing Degrees - Corrigendum (With Lempp)
A note on btt-degrees
Intervals without Critical Triples (with Cholak and Shore)
Every set has a least jump enumeration (With Coles and Slaman)
On Genericity and Ershov's Hierarchy (With Gale)
Maximal contiguous degrees (With Cholak and Walk)
Decomposition and infima in the computably enumerable degrees(With
LaForte and Shore)
Arithmetical Sacks Forcing (With Yu)
There are no maximal low D.C.E. degrees (With Yu)
Lattice Embeddings below a Nonlow2 Recursively Enumerable Degree (With Shore)
Degree Theoretical Definitions of the Low2 Recursively Enumerable Sets(With Shore)
Totally < ww - computably enumerable degrees and m-topped degrees (With Greenberg)
Prompt Simplicity, Array Computability and Cupping (With Greenberg, Miller, and Weber)
On minimal wtt-degrees and computably enumerable Turing degrees (With Ng and Solomon)
Completing Pseudojump Operators (With Jockusch and LaForte)
Working with Strong Reducibilities above Totally Omega-c.e. Degrees (With Barmpalias and Greenberg)
Limits on jump inversion for strong reducibilities (With Csima and Ng)
A $\Delta^0_2$ Set with No Infinite Low Subset in Either It or Its Complement (With Hirschfeldt, Lempp, and Solomon)
Splitting theorems and the jump operator (With Shore)
Extensions of embeddings below computably enumerable degrees (With Greenberg, Lewis, and Montalban)
Totally $\omega$-computably enumerable degrees and bounding critical triples (With Greenberg and Weber)
Degrees of d.c.e. reals (With Wu and Zheng)
Completely mitotic recursively enumerable degrees (With Slaman)
Two theorems on truth table degrees
The degrees of r.e. sets without the universal splitting property
Pseudo-jump operators and SJTHard sets
(with Greenberg)
Minimal pairs in the r.e. truth table degrees (with Keng Meng Ng)
Asymptotic Density and the Ershov Hierarchy (with Carl Jockusch, Tim Mcnicholl and Paul Schupp)
Asymptotic Density and Computable Enumerable Sets (with Carl Jockusch and Paul Schupp)
A Weakly 2-Generic which bounds a Minimal Degree
(with Satyadev Nandakumar)
A transfinite hierarchy of lowness notions in the computably enumerable degrees,unifying classes, and natural definability
(with Noam Greenberg)
A hierarchy of computably enumerable degrees
(with Noam Greenberg)
A Hierarchy of Computably Enumerable Degrees II: Some Recent Developments and New Directions (with Noam Greenberg and Ellen Hammatt)
Splitting into degrees with low computational complexity (with Keng Meng Ng)
Maximality and collapse in the Hierarchy of $\alpha$-c.a.\ Degrees
(with Arthur and Greenberg)
Realizing computably enumerable degrees in separating classes,
(with Cholak, Greenberg, and Turetsky)
Notes on Sacks' Splitting Theorem
(with Ambos-Spies, Monath, and Ng)
A note on realization of index sets in $\Pi_1^0$ classes
(with Melnikov)
On the c.e. degrees realizable in $\Pi_1^0$ classes
(With Csima and Ng)
Fixed-Parameter Tractability and Completeness (With
Fellows)
Fixed-Parameter Tractability and Completeness 1: Basic Results (With Fellows)
Fixed-Parameter Tractability and Completeness 2: On Completeness for W[1] (With Fellows)
Fixed-Parameter Tractability and Completeness 3: Structural Aspects of the W Hirerarchy (With Fellows)
Fixed-Parameter Tractability and Completeness 4: On Completeness for W[P] and PSPACE Analogs (With Abrahamson and Fellows)
Parameterized Complexity: A Framework for Systematically Confronting Computational Intractability (With Fellows and Stege)
Parameterized Circuit Complexity and the W Hierarchy (With Fellows and Regan)
Descriptive complexity and the W Hierarchy
( With Fellows and Regan)
Fixed Parameter Intractability II (Extended Abstract)
(with Abrahamson and Fellows)
The Parameterized Complexity of Relational Database Queries and an Improved Characterization of W[1] (With Fellows and Taylor)
Threshold Dominating Sets and an Improved Characterization of W[2]
(With Fellows)
Parameterized Learning Complexity
(With Evans and Fellows)
The Parameterized Complexity of Sequence Alignment and Consensus
(With Bodlaender, Fellows and Wareham)
The Parameterized Complexity of Sequence Alignment and Consensus
(journal version)
(With Bodlaender, Fellows and Wareham)
The Parameterized Complexity of Short Computation and
Factorization
(With Cai, Chen and Fellows)
Parameterized complexity analysis in computational biology
(With Bodlaender, Fellows Hallett and Wareham)
The Parameterized Complexity of Irredundant sets Parameterized by Size
(With Fellows and Raman)
Advice Classes of Parameterized Tractability
(With Cai, Chen and Fellows)
Advice Classes of Parameterized Tractability-Corrigendum
(With Cai, Chen and Fellows)
On the Structure of Parameterized Problems in NP
(With Cai, Chen and Fellows)
Parameterized Computational Feasibility (With Fellows)
Index Sets and Parametric Reductions (With Fellows)
Computational Tractability: The View From Mars (With Fellows and Stege)
Parameterized Complexity After (Almost) 10 Years: Review and Open Questions (With Fellows)
The parameterized Complexity of Some Fundamental Problems of Linear Codes and Integer Lattices (With Fellows, Whittle, Vardy)
Parameterized Complexity for the Skeptic
Cutting Up Is Hard To Do: the Parameterized Complexity of k-Cut and Related Problems (With Estivill-Castro, Fellows, Prieto-Rodriguez, Rosamond)
Online problems, pathwidth, and persistence (With McCartin)
Some New Directions and Questions in Parameterized Complexity (With McCartin)
Bounded Persistance Pathwidth (With McCartin)
Online Promise Problems with Online Width Metrics (With McCartin)
Parameterized Approximation Problems (With Fellows and McCartin)
Bounded Fixed-Parameter Tractability and Reducibility (With Flum, Grohe, Weyer)
Parameterized Algorithms (With McCartin)
On Problems Without Polynomial Kernels (Journal Version) (With Bodlaender, Fellows, and Hermelin)
Parameterized approximation of dominating set problems(with
Fellows, McCartin, and Rosamond)
Confronting intractability via parameters (with
Thilikos)
A Basic Parameterized Complexity Primer
The Origins of Parameterized Complexity
A parameterized complexity tutorial
Courcelle's Theorem for Triangulations (with Benjamin Burton)
Dynamic Dominating Set and Turbo-Charging Greedy Heuristics (with Judith Egan, Mike Fellows, Fran Rosamond and Peter Shaw)
Myhill-Nerode methods for hypergraphs (with
Ren{\'e} van Bevern, Michael R. Fellows, Serge Gaspers, and Frances A. Rosamond)
Online, Computable, and Punctual Structure Theory (with
Askes)
Randomness, Computability and Density (With Hirschfeldt and Nies)
Randomness and Reducibility (With Hi
rschfeldt and LaForte)
Presentations of computably enumerable reals (With LaForte)
Computably Enumerable Reals and Uniformly Presentable
Ideals (With Terwijn)
K-Trivial Reals and the Jump Traceability Hierarchy (With Barmpalias and Greenberg)
Some Computability Theoretical Aspects of Reals and Randomness
Schnorr Randomness (With Griffiths)
Trivial Reals (With Hirschfeldt, Nies, and Stephan)
The Complexity of the Random Reals (With Yu and Ding)
Some Recent Progress in Algorithmic Randomness
On Schnorr and computable randomness, martingales and machines (With Griffiths and LaForte)
Jump inversions inside effectively closed sets with applications to
randomness (With Barmpalias and Ng)
Relativizing Chaitin's Halting Probability (With Hirschfeldt, Miller, and Nies)
Calibrating Randomness (With Hirschfeldt, Nies, and Terwijn)
Lowness for Computable Machines (With Greenberg, Mihailovic, and Nies)
Lowness and $\Pi_2^0$ Nullsets (With Nies, Weber, and Yu)
Five Lectures on Algorithic Randomness
The Sixth Lecture on Algorithmic Randomness
Turing Degrees of Reals of Positive Effect Packing Dimension (With Greenberg)
Undecidability of the structure of the Solovay degrees of c.e. reals (With Hirschfeldt and LaForte)
Algorithmic Randomness and Computability
Kolmogorov Complexity and Solovay Functions (With Bienvenu)
Solovay Functions and Their Applications to Algorithmic Randomness
(With Bienvenu, Merkle, and Nies)
Binary Subtrees with Few Labelled Paths (With Greenberg, Jockusch, and Milans)
Effective Packing Dimension and Traceability (With Ng)
Lowness for Bounded Randomness
(With Ng)
Lowness for Demuth Randomness
(With Ng)
Characterizing Lowness for Demuth Randomness
(With Bienvenu, Greenberg, Nies and Turetsky)
Strong Jump Traceability II: K-Triviality (With Greenberg)
Strong Jump Traceability I: The Computably Enumerable Case (With Cholak and Greenberg)
Bounded Randomness (With Brodhead and Ng)
Computability, Algorithmic Randomness and Complexity (general article for
``Randomness Through Computation'' by Zenil)
Resolute sequences in initial segment complexity (With Barmpalias)
Exact pairs for the ideal of the -trivial sequences in the Turing degrees
(With Barmpalias)
Randomness, Computation and Mathematics
Computability Theory,
Algorithmic Randomness and Turing's Anticipation
Turing and
Randomness
Random strings and truth table degrees of Turing complete c.e. sets (with
Cai, Epstein, Lempp and Miller)
Avioding effective packing dimension 1 below arraynoncomputable c.e. degrees
(with Stephenson)
Kobayashi Compressability (with Barmpalias)
Multiple Recurrence and Algorithmic Randomness (with Nandakumar and Nies)
Lowness and Bennett Depth (with McInernery and Ng)
Algorithmic Randomness (paper for lay CS audience) (with Hirschfeldt)
Computability and Randomness (paper for lay Math audience) (with Hirschfeldt)
Randomness and Computation (paper for lay logic audience)
Limit Complexities, Minimal Descriptions, and $n$-Randomness (with
Liu, Ng and Turetsky)
Algorithmically random series, and uses of algorithmic randomness in mathematics (with
Greenberg and Tanggara)
Uniformity in Computable Structure Theory (With Hirschfeldt and Khoussainov)
Limitwise monotonic functions and their applications (With Kach and Turetsky)
Computable Categoricity vs Uniform Computable Categoricity (With Lempp, Kach and Turetsky)
The complexity of computable categoricity,
(with Kach, Lempp, Lewis-Pye, Montalban and
Turetsky)
A Friedberg Enumeration of Equivalence Structures (with Ng and Melnikov)
A Question of Kalimullin (with Igusa and Melnikov)
Foundations of Online Structure Theory (With Bazhenov,
Melnikov, and Kalimullin)
Foundations of Online Structure Theory II: The Operator Approach (with Meln
ikov and
Ng)
Graphs are not universal for online computability (With
Harrisison-Trainor, Melnikov, and Turetsky)
Relativizing Computable Categoricity,
(with Harrison-Trainor and Melnikov)
Online, Computable, and Punctual Structure Theory (with
Askes)
Computability Theory and Linear Oderings
Recursive orderings with incomplete successivities(with Moses)
Every recursive boolean algebra is isomorphic to one with incomplete atoms
Orbits of Creative Subspaces
Difference Sets and Computability (With Furedi, Jockusch, and Rubel)
Effective presentability of Boolean algebras of Cantor-Bendixson rank 1 (With Jockusch)
Computability, Definability and Algebraic Structures
Questions in computable algebra and combinatorics (With Remmel)
Invariance and Nonvariance in the Lattice of N01 Classes (With Cholak)
On Presentations of Algebraic Structures
Automorphisms of supermaximal subspaces
Decidability and Computability of Certain Torsion-Free Abelian Groups (With Goncharov, Kach, Knight, Kudinov, Melnikov, and Turetsky)
Euclidean Functions of Computable Euclidean Domians (With Kach)
Degree Spectra of Relations on Boolean Algebras (With Hirschfeldt and Goncharov)
The complexity of the successivity relation in computable linear orderings
(with Lempp and Wu)
The complexity of the successivity relation in computable linear orderings
-Corrigendum
(Correction for the paper above)
(with Lempp and Wu)
Maximal Theories
Space Complexity of Abelian Groups (With Cenzer, Remmel, and Uddin)
On Initial Segments of Computable Linear Orders (With Coles and Khoussainov)
On Self-Embeddings of Computable Linear Orderings (With Jockusch and Miller)
Degree Spectra of Unary Relations on (\omega, \le) (With Khoussainov, Miller, and Yu)
On Computable Self-embeddings of Computable Linear Orderings (With Kastermans and Lempp)
The Isomorphism Problem for Torsion-Free Abelian Groups is Analytic Complete (With Montalban)
Slender Classes (With Montalban)
The Upward Closure of a Perfect Thin Class
(With Greenberg and Miller)
Countable Thin Pi 0 1 Classes(with Cenzer, Jocksuch, Shore)
Effectively Categorical Abelian Groups (With Melnikov)
Computable Completely Decomposable Groups (With Melnikov)
The members of thin and minimal $\Pi^0_1$-classes, their ranks and Turing degrees (With Yang and Wu)
Degrees containing members of thin $\Pi_1^0$ classes are dense and co-dense
(With Yang and Wu)
The Finite Intersection Property and Genericity (
With Diamondstone, Greenberg and Turetsky)
Iterated effective embeddings of abelian $p$-groups (
With Melnikov and Ng)
$\Delta_2^0$ categoricity of equivalence relations
(
With Melnikov and Ng)
The finite intersection property and genericity
With Diamondstone, Greenberg and Turetsky)
Any FIP Real Computes a 1-Generic
(With Cholak and Igusa)
Generic Muchnik reducibility and presentations
of fields
(With Greenberg and Miller)
Notes on Computable Analysis
(With Porter and Day)
Enumerating Abelian $p$-Groups (with Melnikov and Ng)
Categorical Linearly Ordered Structures (with Melnikov and Ng)
Undecidability of L(F infinity) and other lattices of r.e. substructures
Correction to Undecidability of L(F infinity) and other lattices of r.e. substructures
Three Topological Reducibilities for Discontinuous Functions (with Day and Westrick)
Foundations of Online Structure Theory II: The Operator Approach (with Melnikov and
Ng)
Computable Analysis and classification problems (with Melnikov)
Computably Compact Spaces (with Melnikov)
Some Open Questions and Recent Results on Computable Banach Spaces (with Greenberg and Qian)
Splitting theorems in recursion theory(With Stob)
Automorphisms of the lattice of
recursively enumerable sets: Orbits (With Stob)
Automorphisms of the lattice of
recursively enumerable sets: Promptly Simple Sets (With Cholak and Stob)
Splitting Theorems and Low Degrees (with Chih)
There is no Fat Orbit (With Harrington)
Friederg splittings of recursively enumerable sets (With Stob)
Subsets of Hypersimple Sets
On the Universal Splitting Property
Automorphisms of the lattice of
$\Pi_1^0$ classes; perfect thin classes and anc degrees (With Cholak and Herrmann)
Some Orbits for E (With Cholak
and Herrmann)
On The Orbits of Computable Enumerable Sets (With Cholak and Harrington)
The Complexity of Orbits of Computably Enumerable Sets (With Cholak and Harrington)
Lowness Properties for Strong Reducibilities and
The Computational Power of Maximal Sets` (with Ambos-Spies and Monath)
Review of Soare, Lerman-Soare, Cholak and Harrington-Soare, 17 page explanation of the Automorphism Machinery and history
Computability-theoretic and proof-theoretic aspects of partial and linear orderings (With Hirschfeldt, Lempp, and Solomon)
The Proof-Theoretic Strength of the Dushnik-Miller Theorem for Countable Linear Orders(With Lempp)
Reverse mathematics, Archimedian classes and Hahn's theorem (With Solomon)
Reverse Mathematics of the Nielsen-Schreier Theorem(With Hirschfeldt, Lempp, Solomon)
Ideals in Computable Rings(With Lempp and Mileti)
Subspaces of Computable Vector Spaces (With Hirschfeldt, Kach, Lempp, Mileti, and Montalban)
Relationships between Computability-Theoretic Properties of Problems (With Greenberg, Harrison-Trainor, Patey and Turetsky)
Cousin's Lemma in Second Order Arithmetic
(With Barrett and Greenberg)
On Computing Graph Minor Obstruction Sets (With Cattell, Dinneen, Fellows, and Langston)
Undecidability Results for Low Complexity Degree Structures (With Nies)
Uniformly Hard Languages (With Fortnow)
The structure of honest polynomial m-degrees (With Gasarch and Moses)
Nondiamond Theorems for Polynomial Time Reducibility
On honest polynomial reductions relativizations, and P=NP
(With Gasarch, Homer, Moses)
Undecidability Results for Low Complexity Time Classes (With Nies)
A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second Order Ideals (With Courcelle and Fellows)
An invitation to structural complexity
On Low for Speed Oracles (with Bienvenu)
A Minimal Set Low for Speed (with Harrison-Trainor)
On co-simple isols and their intersection types
(with Slaman)
Tabular degrees in alpha recursion theory (with Bailey)
Sound, totally sound and unsound recursive equivalence types
On Hyper-Torre Isols
On Ramsey-type Theorems and their Applications