Rod Downey's Publications for Download

Degree Theory
Randomness
Parameterized Complexity
Computable Model Theory
Effective Algebra 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)
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
Minimal Degrees Recursive in 1-Generic 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 Nonlow₂ Recursively Enumerable Degree (With Shore)
Degree Theoretical Definitions of the Low2 Recursively Enumerable Sets(With Shore)
Totally < w^w - 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 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)

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 Reagan)
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)
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)

Randomness, Computability and Density (With Hirschfeldt and Nies)
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)
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)
Bounded Randomness (With Brodhead and Ng)
Computability, Algorithmic Randomness and Complexity (general article for ``Randomness Through Computation'' by Zenil)

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)

Computability Theory and Linear Oderings
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)
Maximal Theories
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)

Splitting theorems in recursion theory(With Stob)
There is no Fat Orbit (With Harrington)
Friederg splittings of recursively enumerable sets (With Stob)
Subsets of Hypersimple Sets
On the Universal Splitting Property
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)

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)
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

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