3 citations · 3 across the 2 of their papers we have counts for
4 papers
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…
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…
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…
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…