16 citations · 54 across the 28 of their papers we have counts for
5 papers · 1 filter
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…
Separations of non-monotonic randomness notions
Laurent Bienvenu, Rupert Hoelzl, Thorsten Kraling +1
In the theory of algorithmic randomness, several notions of random sequence are defined via a game-theoretic approach, and the notions that received most attention are perhaps Mart…
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…
Limit complexities revisited
Laurent Bienvenu, Andrej Muchnik, Alexander Shen +1
The main goal of this paper is to put some known results in a common perspective and to simplify their proofs. We start with a simple proof of a result from (Vereshchagin, 2002) sa…
Constructive Dimension and Turing Degrees
Laurent Bienvenu, David Doty, Frank Stephan
This paper examines the constructive Hausdorff and packing dimensions of Turing degrees. The main result is that every infinite sequence S with constructive Hausdorff dimension dim…