License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2017.17
URN: urn:nbn:de:0030-drops-75222
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7522/
Go to the corresponding LIPIcs Volume Portal


Milovanov, Alexey ; Vereshchagin, Nikolay

Stochasticity in Algorithmic Statistics for Polynomial Time

pdf-format:
LIPIcs-CCC-2017-17.pdf (0.5 MB)


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.

BibTeX - Entry

@InProceedings{milovanov_et_al:LIPIcs:2017:7522,
  author =	{Alexey Milovanov and Nikolay Vereshchagin},
  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 =	{Ryan O'Donnell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7522},
  URN =		{urn:nbn:de:0030-drops-75222},
  doi =		{10.4230/LIPIcs.CCC.2017.17},
  annote =	{Keywords: Algorithmic Statistics, Kolmogorov complexity, elusive set, distinguishing complexity}
}

Keywords: Algorithmic Statistics, Kolmogorov complexity, elusive set, distinguishing complexity
Seminar: 32nd Computational Complexity Conference (CCC 2017)
Issue Date: 2017
Date of publication: 21.07.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI