# 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

**DEGREE THEORY**

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)

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

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 Nonlow_{2} 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 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)

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)

**PARAMETERIZED COMPLEXITY**

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)

**RANDOMNESS**

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)

**COMPUTABLE MODEL THEORY**

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)

Graphs are not universal for online computability (With Harr
ison-Trainor, Melnikov, and Turetsky)

**EFFECTIVE ALGEBRA, ANALYSIS, and COMPUTABLE COMBINATORICS**

Computability Theory and Linear Oderings

Recursive orderings with incomplete successivities

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)

**LATTICE OF COMPUTABLY ENUMERABLE SETS**

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)

On The Orbits of Computable Enumerable Sets (With Cholak and Harrington)

The Complexity of Orbits of Computably Enumerable Sets (With Cholak and Harrington)

Review of Soare, Lerman-Soare, Cholak and Harrington-Soare, 17 page explanation of the Automorphism Machinery and history

**REVERSE MATHEMATICS**

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)

**COMPLEXITY THEORY MISCELLANEOUS**

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)

**COMPUTABILITY MISCELLANEOUS**

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

**MISCELLANEOUS**

On Ramsey-type Theorems and their Applications