55 citations · 164 across the 24 of their papers we have counts for
6 papers · 2 filters
Muchnik degrees and cardinal characteristics
Benoit Monin, André Nies
For let be the mass problem of infinite bit sequences~ (i.e., -valued functions) such that for each computable bit sequence , the bit s…
Closure of resource-bounded randomness notions under polynomial time permutations
Andre Nies, Frank Stephan
An infinite bit sequence is called recursively random if no computable strategy betting along the sequence has unbounded capital. It is well-known that the property of recursive ra…
Martin-Löf reducibility and cost functions
Noam Greenberg, Joseph S. Miller, Andre Nies +1
Martin-Löf (ML)-reducibility compares -trivial sets by examining the Martin-Löf random sequences that compute them. We show that every -trivial set is computable from a c.e.\…
Computing from projections of random points: a dense hierarchy of subideals of the -trivial degrees
Noam Greenberg, Joseph S. Miller, Andre Nies
We study the sets that are computable from both halves of some (Martin-Löf) random sequence, which we call \emph{-bases}. We show that the collection of such sets forms an ide…
The reverse mathematics of theorems of Jordan and Lebesgue
André Nies, Marcus A. Triplett, Keita Yokoyama
The Jordan decomposition theorem states that every function of bounded variation can be written as the difference of two non-decreasing functions. C…
Calculus of Cost Functions
Andre Nies
Cost functions provide a framework for constructions of sets Turing below the halting problem that are close to computable. We carry out a systematic study of cost functions. We re…