16 citations · 45 across the 11 of their papers we have counts for
15 papers
Cousin's lemma in second-order arithmetic
Jordan Mitchell Barrett, Rodney G. Downey, Noam Greenberg
Cousin's lemma is a compactness principle that naturally arises when studying the gauge integral, a generalisation of the Lebesgue integral. We study the axiomatic strength of Cous…
Realizing Computably Enumerable Degrees in Separating Classes
Peter Cholak, Rod Downey, Noam Greenberg +1
We investigate what collections of c.e.\ Turing degrees can be realised as the collection of elements of a separating class of c.e.\ degree. We show that for every c.e.\ de…
Three topological reducibilities for discontinuous functions
Adam R. Day, Rod Downey, Linda Brown Westrick
We define a family of three related reducibilities, , and , for arbitrary functions , where is a compact separable metric…
On low for speed oracles
Laurent Bienvenu, Rod Downey
Relativizing computations of Turing machines to an oracle is a central concept in the theory of computation, both in complexity theory and in computability theory(!). Inspired by l…
Kobayashi compressibility
George Barmpalias, Rodney G. Downey
Kobayashi introduced a uniform notion of compressibility of infinite binary sequences in terms of relative Turing computations with sub-identity use of the oracle. Kobayashi compre…
Multiple Recurrence and Algorithmic Randomness
Rodney G. Downey, Satyadev Nandakumar, Andre Nies
This work contributes to the programme of studying effective versions of "almost everywhere" theorems in analysis and ergodic theory via algorithmic randomness. We determine the le…
Integer Valued Betting strategies and Turing Degrees
George Barmpalias, Rod G. Downey, Michael McInerney
Betting strategies are often expressed formally as martingales. A martingale is called integer-valued if each bet must be an integer value. Integer-valued strategies correspond to…
Random strings and tt-degrees of Turing complete C.E. sets
Mingzhong Cai, Rodney G Downey, Rachel Epstein +2
We investigate the truth-table degrees of (co-)c.e.\ sets, in particular, sets of random strings. It is known that the set of random strings with respect to any universal prefix-fr…
Courcelle's theorem for triangulations
Benjamin A. Burton, Rodney G. Downey
In graph theory, Courcelle's theorem essentially states that, if an algorithmic problem can be formulated in monadic second-order logic, then it can be solved in linear time for gr…
Asymptotic Density and Computably Enumerable Sets
Rodney G. Downey, Carl G. Jockusch, Paul E. Schupp
We study connections between classical asymptotic density and c.e. sets. We prove that a c.e. Turing degree d is not low if and only if d contains a c.e. set A of density 1 which h…
Myhill-Nerode methods for hypergraphs
René van Bevern, Rodney G. Downey, Michael R. Fellows +2
We give an analog of the Myhill-Nerode methods from formal language theory for hypergraphs and use it to derive the following results for two NP-hard hypergraph problems: * We prov…
Pseudo-jump inversion and SJT-hard sets
Rodney G. Downey, Noam Greenberg
There are noncomputable c.e.\ sets, computable from every SJT-hard c.e.\ set. This yields a natural pseudo-jump operator, increasing on all sets, which cannot be inverted back to a…
Confronting Intractability via Parameters
Rodney G. Downey, Dimitrios M. Thilikos
One approach to confronting computational hardness is to try to understand the contribution of various parameters to the running time of algorithms and the complexity of computatio…
Kolmogorov Complexity and Solovay Functions
Laurent Bienvenu, Rod Downey
Solovay proved that there exists a computable upper bound f of the prefix-free Kolmogorov complexity function K such that f (x) = K(x) for infinitely many x. In this paper, we cons…
The Complexity of Orbits of Computably Enumerable Sets
Peter A. Cholak, Rod Downey, Leo Harrington
The goal of this paper is to announce there is a single orbit of the c.e. sets with inclusion, $\E$, such that the question of membership in this orbit is -complete. This re…