Document

**Published in:** LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Can a probabilistic gambler get arbitrarily rich when all deterministic gamblers fail? We study this problem in the context of algorithmic randomness, introducing a new notion - almost everywhere computable randomness. A binary sequence X is a.e. computably random if there is no probabilistic computable strategy which is total and succeeds on X for positive measure of oracles. Using the fireworks technique we construct a sequence which is partial computably random but not a.e. computably random. We also prove the separation between a.e. computable randomness and partial computable randomness, which happens exactly in the uniformly almost everywhere dominating Turing degrees.

Laurent Bienvenu, Valentino Delle Rose, and Tomasz Steifer. Probabilistic vs Deterministic Gamblers. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bienvenu_et_al:LIPIcs.STACS.2022.11, author = {Bienvenu, Laurent and Delle Rose, Valentino and Steifer, Tomasz}, title = {{Probabilistic vs Deterministic Gamblers}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {11:1--11:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.11}, URN = {urn:nbn:de:0030-drops-158210}, doi = {10.4230/LIPIcs.STACS.2022.11}, annote = {Keywords: Algorithmic randomness, Martingales, Probabilistic computation, Almost everywhere domination} }

Document

**Published in:** LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

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 lowness notions from computability theory, Allender introduced the concept of "low for speed" oracles. An oracle A is low for speed if relativizing to A has essentially no effect on computational complexity, meaning that if a decidable language can be decided in time f(n) with access to oracle A, then it can be decided in time poly(f(n)) without any oracle. The existence of non-computable such A's was later proven by Bayer and Slaman, who even constructed a computably enumerable one, and exhibited a number of properties of these oracles as well as interesting connections with computability theory. In this paper, we pursue this line of research, answering the questions left by Bayer and Slaman and give further evidence that the structure of the class of low for speed oracles is a very rich one.

Laurent Bienvenu and Rodney Downey. On Low for Speed Oracles. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bienvenu_et_al:LIPIcs.STACS.2018.15, author = {Bienvenu, Laurent and Downey, Rodney}, title = {{On Low for Speed Oracles}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {15:1--15:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.15}, URN = {urn:nbn:de:0030-drops-85226}, doi = {10.4230/LIPIcs.STACS.2018.15}, annote = {Keywords: Lowness for speed, Oracle computations, Turing degrees} }

Document

**Published in:** Dagstuhl Reports, Volume 2, Issue 1 (2012)

Research on the notions of information and randomness has drawn on methods and ideas from computability theory and cumputational complexity, as well as core mathematical subjects like measure theory and information theory. The Dagstuhl seminar 12021 ``Computability, Complexity and Randomness'' was aimed to meet people and ideas in these areas to share new results and discuss open problems.
This report collects the material presented during the course of the seminar.

Veronica Becher, Laurent Bienvenu, Rodney Downey, and Elvira Mayordomo. Computability, Complexity and Randomness (Dagstuhl Seminar 12021). In Dagstuhl Reports, Volume 2, Issue 1, pp. 19-38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{becher_et_al:DagRep.2.1.19, author = {Becher, Veronica and Bienvenu, Laurent and Downey, Rodney and Mayordomo, Elvira}, title = {{Computability, Complexity and Randomness (Dagstuhl Seminar 12021)}}, pages = {19--38}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2012}, volume = {2}, number = {1}, editor = {Becher, Veronica and Bienvenu, Laurent and Downey, Rodney and Mayordomo, Elvira}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.1.19}, URN = {urn:nbn:de:0030-drops-34555}, doi = {10.4230/DagRep.2.1.19}, annote = {Keywords: algorithmic randomness, computability theory, computationl complexity, Kolmogorov complexity, algorithmic information theory} }

Document

**Published in:** LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

The Denjoy-Young-Saks Theorem from classical analysis states that for an arbitrary function f:R->R, the Denjoy alternative holds outside a null set, i.e., for almost every real x, either the derivative of f exists at x, or the derivative fails to exist in the worst possible way: the limit superior of the slopes around x equals +infinity, and the limit inferior -infinity. Algorithmic randomness allows us to define randomness notions giving rise to different concepts of almost everywhere. It is then natural to wonder which of these concepts corresponds to the almost everywhere notion appearing in the Denjoy-Young-Saks theorem. To answer this question Demuth investigated effective versions of the theorem and proved that Demuth randomness is strong enough to ensure the Denjoy alternative for Markov computable functions. In this paper, we show that the set of these points is indeed strictly bigger than the set of Demuth random reals - showing that Demuth's sufficient condition was too strong - and moreover is incomparable with Martin-Löf randomness; meaning in particular that it does not correspond to any known set of random reals. To prove these two theorems, we study density-type theorems, such as the Lebesgue density theorem and obtain results of independent interest. We show for example that the classical notion of Lebesgue density can be characterized by the only very recently defined notion of difference randomness. This is to our knowledge the first analytical characterization of difference randomness. We also consider the concept of porous points, a special type of Lebesgue nondensity points that are well-behaved in the sense that the "density holes" around the point are continuous intervals whose length follows a certain systematic rule. An essential part of our proof will be to argue that porous points of effectively closed classes can never be difference random.

Laurent Bienvenu, Rupert Hölzl, Joseph S. Miller, and André Nies. The Denjoy alternative for computable functions. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 543-554, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{bienvenu_et_al:LIPIcs.STACS.2012.543, author = {Bienvenu, Laurent and H\"{o}lzl, Rupert and Miller, Joseph S. and Nies, Andr\'{e}}, title = {{The Denjoy alternative for computable functions}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {543--554}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.543}, URN = {urn:nbn:de:0030-drops-34095}, doi = {10.4230/LIPIcs.STACS.2012.543}, annote = {Keywords: Differentiability, Denjoy alternative, density, porosity, randomness} }

Document

**Published in:** LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

As part of his groundbreaking work on algorithmic randomness, Solovay demonstrated in the 1970s the remarkable fact that there are computable upper bounds of prefix-free Kolmogorov complexity $K$ that are tight on infinitely many values (up to an additive constant). Such computable upper bounds are called Solovay functions. Recent work of Bienvenu and Downey~[STACS 2009, LIPIcs 3, pp 147-158] indicates that Solovay functions are deeply connected with central concepts of algorithmic randomness such as $Omega$ numbers, K-triviality, and Martin-Loef randomness.
In what follows, among other results we answer two open problems posed by Bienvenu and Downey about the definition of $K$-triviality and about the Gacs-Miller-Yu characterization of Martin-Loef randomness. The former defines a sequence A to be K-trivial if K(A|n) <=^+ K(n), the latter asserts that a sequence A is Martin-Loef random iff C(A|n) >=^+ n-K(n). So both involve the noncomputable function K. As our main results we show that in both cases K(n) can be equivalently replaced by any Solovay function, and, what is more, that among all computable functions such a replacement is possible exactly for the Solovay functions. Moreover, similar statements hold for the larger class of all right-c.e. in place of the computable functions. These full characterizations, besides having significant theoretical interest on their own, will be useful as tools when working with K-trivial and Martin-Loef random sequences.

Laurent Bienvenu, Wolfgang Merkle, and Andre Nies. Solovay functions and K-triviality. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 452-463, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{bienvenu_et_al:LIPIcs.STACS.2011.452, author = {Bienvenu, Laurent and Merkle, Wolfgang and Nies, Andre}, title = {{Solovay functions and K-triviality}}, booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)}, pages = {452--463}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-25-5}, ISSN = {1868-8969}, year = {2011}, volume = {9}, editor = {Schwentick, Thomas and D\"{u}rr, Christoph}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.452}, URN = {urn:nbn:de:0030-drops-30345}, doi = {10.4230/LIPIcs.STACS.2011.452}, annote = {Keywords: Algorithmic randomness, Kolmogorov complexity, K-triviality} }

Document

**Published in:** OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

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 Martin-L\"of randomness
and computable randomness. The latter notion was introduced by Schnorr and is rather natural: an infinite binary sequence is computably random if no total computable strategy succeeds on it by betting on bits in order. However, computably random sequences can have properties that one may consider to be incompatible with being random, in particular, there are computably random sequences that are highly compressible. The concept of Martin-L\"of randomness is much better behaved in this and other respects, on the other hand its definition in terms of martingales is considerably less natural.
Muchnik, elaborating on ideas of Kolmogorov and Loveland, refined Schnorr's model by also allowing non-monotonic strategies, i.e.\ strategies that do not bet on bits in order. The subsequent ``non-monotonic'' notion of randomness, now called Kolmogorov-Loveland-randomness, has been shown to be quite close to Martin-L\"of randomness, but whether these two classes coincide remains a fundamental open question.
In order to get a better understanding of non-monotonic randomness notions, Miller and Nies introduced some interesting intermediate concepts, where one only allows non-adaptive strategies, i.e., strategies that can still bet non-monotonically, but such that the sequence of betting positions is known in advance (and computable). Recently, these notions were shown by Kastermans and Lempp to differ from Martin-L\"of randomness. We continue the study of the non-monotonic randomness notions introduced by Miller and Nies and obtain results about the Kolmogorov complexities of initial segments that may and may not occur for such sequences, where these results then imply a complete classification of these randomness notions by order of strength.

Laurent Bienvenu, Rupert Hölzl, Thorsten Kräling, and Wolfgang Merkle. Separations of Non-monotonic Randomness Notions. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 71-82, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{bienvenu_et_al:OASIcs.CCA.2009.2260, author = {Bienvenu, Laurent and H\"{o}lzl, Rupert and Kr\"{a}ling, Thorsten and Merkle, Wolfgang}, title = {{Separations of Non-monotonic Randomness Notions}}, booktitle = {6th International Conference on Computability and Complexity in Analysis (CCA'09)}, pages = {71--82}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-939897-12-5}, ISSN = {2190-6807}, year = {2009}, volume = {11}, editor = {Bauer, Andrej and Hertling, Peter and Ko, Ker-I}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2260}, URN = {urn:nbn:de:0030-drops-22601}, doi = {10.4230/OASIcs.CCA.2009.2260}, annote = {Keywords: Martin-L\"{o}f randomness, Kolmogorov-Loveland randomness, Kolmogorov complexity, martingales, betting strategies} }

Document

**Published in:** LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Solovay (1975) 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 consider the class of computable functions~$f$ such that $K(x) \leq f(x)+O(1)$ for all~$x$ and $f(x) \leq K(x)+O(1)$ for infinitely many~$x$, which we call Solovay functions. We show that Solovay functions present interesting connections with randomness notions such as Martin-L\"of randomness and K-triviality.

Laurent Bienvenu and Rod Downey. Kolmogorov Complexity and Solovay Functions. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 147-158, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{bienvenu_et_al:LIPIcs.STACS.2009.1810, author = {Bienvenu, Laurent and Downey, Rod}, title = {{Kolmogorov Complexity and Solovay Functions}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {147--158}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1810}, URN = {urn:nbn:de:0030-drops-18107}, doi = {10.4230/LIPIcs.STACS.2009.1810}, annote = {Keywords: Algorithmic randomness, Kolmogorov complexity, K-triviality} }

Document

**Published in:** LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

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)
saying that $limsup_{nKS(x|n)$ (here $KS(x|n)$ is conditional
(plain) Kolmogorov complexity of $x$ when $n$ is known) equals
$KS^{mathbf{0'(x)$, the plain Kolmogorov complexity with
$mathbf{0'$-oracle.
Then we use the same argument to prove similar results for prefix
complexity (and also improve results of (Muchnik, 1987) about limit
frequencies), a priori probability on binary tree and measure of
effectively open sets. As a by-product, we get a criterion of
$mathbf{0'$ Martin-L"of randomness (called also $2$-randomness)
proved in (Miller, 2004): a sequence $omega$ is $2$-random if and
only if there exists $c$ such that any prefix $x$ of $omega$ is a
prefix of some string $y$ such that $KS(y)ge |y|-c$. (In the
1960ies this property was suggested in (Kolmogorov, 1968) as one of
possible randomness definitions; its equivalence to $2$-randomness
was shown in (Miller, 2004) while proving another $2$-randomness
criterion (see also (Nies et al. 2005)): $omega$ is $2$-random if
and only if $KS(x)ge |x|-c$ for some $c$ and infinitely many
prefixes $x$ of $omega$.
Finally, we show that the low-basis theorem can be used to get
alternative proofs for these results and to improve the result
about effectively open sets; this stronger version implies the
$2$-randomness criterion mentioned in the previous sentence.

Laurent Bienvenu, Andrej Muchnik, Alexander Shen, and Nikolay Veraschagin. Limit complexities revisited. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 73-84, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{bienvenu_et_al:LIPIcs.STACS.2008.1335, author = {Bienvenu, Laurent and Muchnik, Andrej and Shen, Alexander and Veraschagin, Nikolay}, title = {{Limit complexities revisited}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {73--84}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1335}, URN = {urn:nbn:de:0030-drops-13350}, doi = {10.4230/LIPIcs.STACS.2008.1335}, annote = {Keywords: Kolmogorov complexity, limit complexities, limit frequencies, 2-randomness, low basis} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail