2 Search Results for "Vereshchagin, Nikolay"

Document
DOI: 10.4230/LIPIcs.CCC.2017.17
Stochasticity in Algorithmic Statistics for Polynomial Time

Authors: Alexey Milovanov and Nikolay Vereshchagin

Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)

Abstract
A fundamental notion in Algorithmic Statistics is that of a stochastic object, i.e., an object having a simple plausible explanation. Informally, a probability distribution is a plausible explanation for x if it looks likely that x was drawn at random with respect to that distribution. In this paper, we suggest three definitions of a plausible statistical hypothesis for Algorithmic Statistics with polynomial time bounds, which are called acceptability, plausibility and optimality. Roughly speaking, a probability distribution m is called an acceptable explanation for x, if x possesses all properties decidable by short programs in a short time and shared by almost all objects (with respect to m). Plausibility is a similar notion, however this time we require x to possess all properties T decidable even by long programs in a short time and shared by almost all objects. To compensate the increase in program length, we strengthen the notion of `almost all' - the longer the program recognizing the property is, the more objects must share the property. Finally, a probability distribution m is called an optimal explanation for x if m(x) is large. Almost all our results hold under some plausible complexity theoretic assumptions. Our main result states that for acceptability and plausibility there are infinitely many non-stochastic objects, i.e. objects that do not have simple plausible (acceptable) explanations. Using the same techniques, we show that the distinguishing complexity of a string x can be super-logarithmically less than the conditional complexity of x with condition r for almost all r (for polynomial time bounded programs). Finally, we study relationships between the introduced notions.
Cite as

Alexey Milovanov and Nikolay Vereshchagin. Stochasticity in Algorithmic Statistics for Polynomial Time. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{milovanov_et_al:LIPIcs.CCC.2017.17,
  author =	{Milovanov, Alexey and Vereshchagin, Nikolay},
  title =	{{Stochasticity in Algorithmic Statistics for Polynomial Time}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{17:1--17:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{O'Donnell, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.17},
  URN =		{urn:nbn:de:0030-drops-75222},
  doi =		{10.4230/LIPIcs.CCC.2017.17},
  annote =	{Keywords: Algorithmic Statistics, Kolmogorov complexity, elusive set, distinguishing complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1335
Limit complexities revisited

Authors: Laurent Bienvenu, Andrej Muchnik, Alexander Shen, and Nikolay Veraschagin

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

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

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-dev.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}
}
  • Refine by Author
  • 1 Bienvenu, Laurent
  • 1 Milovanov, Alexey
  • 1 Muchnik, Andrej
  • 1 Shen, Alexander
  • 1 Veraschagin, Nikolay
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 2 Kolmogorov complexity
  • 1 2-randomness
  • 1 Algorithmic Statistics
  • 1 distinguishing complexity
  • 1 elusive set
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2008
  • 1 2017

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 Imprint Privacy Contact