2 citations · 3 across the 4 of their papers we have counts for
5 papers
Limit Complexities, Minimal Descriptions, and -Randomness
Rodney Downey, Lu Liu, Keng Meng Ng +1
Let denote prefix-free Kolmogorov Complexity, and denote it relative to an oracle . We show that for any , is definable purely in terms of the…
A minimal set low for speed
Rod Downey, Matthew Harrison-Trainor
An oracle is low-for-speed if it is unable to speed up the computation of a set which is already computable: if a decidable language can be decided in time using as…
Relationships between computability-theoretic properties of problems
Rod Downey, Noam Greenberg, Matthew Harrison-Trainor +2
A problem is a multivalued function from a set of \emph{instances} to a set of \emph{solutions}. We consider only instances and solutions coded by sets of integers. A problem admit…
Solovay functions and their applications in algorithmic randomness
Laurent Bienvenu, Rod Downey, Wolfgang Merkle +1
Classical versions of Kolmogorov complexity are incomputable. Nevertheless, in 1975 Solovay showed that there are computable functions such that for infinitely many st…
On the Orbits of Computably Enumerable Sets
Peter Cholak, Rod Downey, Leo Harrington
The goal of this paper is to show there is a single orbit of the c.e. sets with inclusion, , such that the question of membership in this orbit is -complete. Th…