Search Results

Documents authored by Nies, André

Found 2 Possible Name Variants:

Nies, Andre

Document
DOI: 10.4230/LIPIcs.STACS.2020.55
Randomness and Initial Segment Complexity for Probability Measures

Authors: André Nies and Frank Stephan

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
We study algorithmic randomness properties for probability measures on Cantor space. We say that a measure μ on the space of infinite bit sequences is Martin-Löf absolutely continuous if the non-Martin-Löf random bit sequences form a null set with respect to μ. We think of this as a weak randomness notion for measures. We begin with examples, and a robustness property related to Solovay tests. Our main work connects our property to the growth of the initial segment complexity for measures μ; the latter is defined as a μ-average over the complexity of strings of the same length. We show that a maximal growth implies our weak randomness property, but also that both implications of the Levin-Schnorr theorem fail. We briefly discuss K-triviality for measures, which means that the growth of initial segment complexity is as slow as possible. We show that full Martin-Löf randomness of a measure implies Martin-Löf absolute continuity; the converse fails because only the latter property is compatible with having atoms. In a final section we consider weak randomness relative to a general ergodic computable measure. We seek appropriate effective versions of the Shannon-McMillan-Breiman theorem and the Brudno theorem where the bit sequences are replaced by measures.
Cite as

André Nies and Frank Stephan. Randomness and Initial Segment Complexity for Probability Measures. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 55:1-55:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{nies_et_al:LIPIcs.STACS.2020.55,
  author =	{Nies, Andr\'{e} and Stephan, Frank},
  title =	{{Randomness and Initial Segment Complexity for Probability Measures}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{55:1--55:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.55},
  URN =		{urn:nbn:de:0030-drops-119168},
  doi =		{10.4230/LIPIcs.STACS.2020.55},
  annote =	{Keywords: algorithmic randomness, probability measure on Cantor space, Kolmogorov complexity, statistical superposition, quantum states}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.51
Closure of Resource-Bounded Randomness Notions Under Polynomial-Time Permutations

Authors: André Nies and Frank Stephan

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

Abstract
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 randomness is closed under computable permutations. We investigate analogous statements for randomness notions defined by betting strategies that are computable within resource bounds. Suppose that S is a polynomial time computable permutation of the set of strings over the unary alphabet (identified with the set of natural numbers). If the inverse of S is not polynomially bounded, it is not hard to build a polynomial time random bit sequence Z such that Z o S is not polynomial time random. So one should only consider permutations S satisfying the extra condition that the inverse is polynomially bounded. Now the closure depends on additional assumptions in complexity theory. Our first main result, Theorem 4, shows that if BPP contains a superpolynomial deterministic time class, then polynomial time randomness is not preserved by some permutation S such that in fact both S and its inverse are in P. Our second result, Theorem 11, shows that polynomial space randomness is preserved by polynomial time permutations with polynomially bounded inverse, so if P = PSPACE then polynomial time randomness is preserved.
Cite as

André Nies and Frank Stephan. Closure of Resource-Bounded Randomness Notions Under Polynomial-Time Permutations. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 51:1-51:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{nies_et_al:LIPIcs.STACS.2018.51,
  author =	{Nies, Andr\'{e} and Stephan, Frank},
  title =	{{Closure of Resource-Bounded Randomness Notions Under Polynomial-Time Permutations}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{51:1--51:10},
  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.51},
  URN =		{urn:nbn:de:0030-drops-84938},
  doi =		{10.4230/LIPIcs.STACS.2018.51},
  annote =	{Keywords: Computational complexity, Randomness via resource-bounded betting strategies, Martingales, Closure under permutations}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.602
Differentiability of polynomial time computable functions

Authors: André Nies

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
We show that a real z is polynomial time random if and only if each nondecreasing polynomial time computable function is differentiable at z. This establishes an analog in feasible analysis of a recent result of Brattka, Miller and Nies, who characterized computable randomness in terms of differentiability of nondecreasing computable functions. Further, we show that a Martin-Loef random real z is a density-one point if and only if each interval-c.e. function is differentiable at z. (To say z is a density-one point means that every effectively closed class containing z has density one at z. The interval-c.e. functions are, essentially, the variation functions of computable functions.) The proofs are related: they both make use of the analytical concept of porosity in novel ways, and both use a basic geometric fact on shifting dyadic intervals by 1/3.
Cite as

André Nies. Differentiability of polynomial time computable functions. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 602-613, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{nies:LIPIcs.STACS.2014.602,
  author =	{Nies, Andr\'{e}},
  title =	{{Differentiability of polynomial time computable functions}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{602--613},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.602},
  URN =		{urn:nbn:de:0030-drops-44919},
  doi =		{10.4230/LIPIcs.STACS.2014.602},
  annote =	{Keywords: Polynomial time randomness, feasible analysis, differentiability, porosity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.543
The Denjoy alternative for computable functions

Authors: Laurent Bienvenu, Rupert Hölzl, Joseph S. Miller, and André Nies

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.STACS.2011.452
Solovay functions and K-triviality

Authors: Laurent Bienvenu, Wolfgang Merkle, and Andre Nies

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

Abstract
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.
Cite as

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}
}

Nies, André

Document
DOI: 10.4230/LIPIcs.STACS.2020.55
Randomness and Initial Segment Complexity for Probability Measures

Authors: André Nies and Frank Stephan

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
We study algorithmic randomness properties for probability measures on Cantor space. We say that a measure μ on the space of infinite bit sequences is Martin-Löf absolutely continuous if the non-Martin-Löf random bit sequences form a null set with respect to μ. We think of this as a weak randomness notion for measures. We begin with examples, and a robustness property related to Solovay tests. Our main work connects our property to the growth of the initial segment complexity for measures μ; the latter is defined as a μ-average over the complexity of strings of the same length. We show that a maximal growth implies our weak randomness property, but also that both implications of the Levin-Schnorr theorem fail. We briefly discuss K-triviality for measures, which means that the growth of initial segment complexity is as slow as possible. We show that full Martin-Löf randomness of a measure implies Martin-Löf absolute continuity; the converse fails because only the latter property is compatible with having atoms. In a final section we consider weak randomness relative to a general ergodic computable measure. We seek appropriate effective versions of the Shannon-McMillan-Breiman theorem and the Brudno theorem where the bit sequences are replaced by measures.
Cite as

André Nies and Frank Stephan. Randomness and Initial Segment Complexity for Probability Measures. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 55:1-55:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{nies_et_al:LIPIcs.STACS.2020.55,
  author =	{Nies, Andr\'{e} and Stephan, Frank},
  title =	{{Randomness and Initial Segment Complexity for Probability Measures}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{55:1--55:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.55},
  URN =		{urn:nbn:de:0030-drops-119168},
  doi =		{10.4230/LIPIcs.STACS.2020.55},
  annote =	{Keywords: algorithmic randomness, probability measure on Cantor space, Kolmogorov complexity, statistical superposition, quantum states}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.51
Closure of Resource-Bounded Randomness Notions Under Polynomial-Time Permutations

Authors: André Nies and Frank Stephan

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

Abstract
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 randomness is closed under computable permutations. We investigate analogous statements for randomness notions defined by betting strategies that are computable within resource bounds. Suppose that S is a polynomial time computable permutation of the set of strings over the unary alphabet (identified with the set of natural numbers). If the inverse of S is not polynomially bounded, it is not hard to build a polynomial time random bit sequence Z such that Z o S is not polynomial time random. So one should only consider permutations S satisfying the extra condition that the inverse is polynomially bounded. Now the closure depends on additional assumptions in complexity theory. Our first main result, Theorem 4, shows that if BPP contains a superpolynomial deterministic time class, then polynomial time randomness is not preserved by some permutation S such that in fact both S and its inverse are in P. Our second result, Theorem 11, shows that polynomial space randomness is preserved by polynomial time permutations with polynomially bounded inverse, so if P = PSPACE then polynomial time randomness is preserved.
Cite as

André Nies and Frank Stephan. Closure of Resource-Bounded Randomness Notions Under Polynomial-Time Permutations. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 51:1-51:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{nies_et_al:LIPIcs.STACS.2018.51,
  author =	{Nies, Andr\'{e} and Stephan, Frank},
  title =	{{Closure of Resource-Bounded Randomness Notions Under Polynomial-Time Permutations}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{51:1--51:10},
  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.51},
  URN =		{urn:nbn:de:0030-drops-84938},
  doi =		{10.4230/LIPIcs.STACS.2018.51},
  annote =	{Keywords: Computational complexity, Randomness via resource-bounded betting strategies, Martingales, Closure under permutations}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.602
Differentiability of polynomial time computable functions

Authors: André Nies

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
We show that a real z is polynomial time random if and only if each nondecreasing polynomial time computable function is differentiable at z. This establishes an analog in feasible analysis of a recent result of Brattka, Miller and Nies, who characterized computable randomness in terms of differentiability of nondecreasing computable functions. Further, we show that a Martin-Loef random real z is a density-one point if and only if each interval-c.e. function is differentiable at z. (To say z is a density-one point means that every effectively closed class containing z has density one at z. The interval-c.e. functions are, essentially, the variation functions of computable functions.) The proofs are related: they both make use of the analytical concept of porosity in novel ways, and both use a basic geometric fact on shifting dyadic intervals by 1/3.
Cite as

André Nies. Differentiability of polynomial time computable functions. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 602-613, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{nies:LIPIcs.STACS.2014.602,
  author =	{Nies, Andr\'{e}},
  title =	{{Differentiability of polynomial time computable functions}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{602--613},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.602},
  URN =		{urn:nbn:de:0030-drops-44919},
  doi =		{10.4230/LIPIcs.STACS.2014.602},
  annote =	{Keywords: Polynomial time randomness, feasible analysis, differentiability, porosity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.543
The Denjoy alternative for computable functions

Authors: Laurent Bienvenu, Rupert Hölzl, Joseph S. Miller, and André Nies

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.STACS.2011.452
Solovay functions and K-triviality

Authors: Laurent Bienvenu, Wolfgang Merkle, and Andre Nies

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

Abstract
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.
Cite as

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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact