{
  "id": "1009.4995",
  "version": "v1",
  "published": "2010-09-25T08:44:10.000Z",
  "updated": "2010-09-25T08:44:10.000Z",
  "title": "Kolmogorov complexity, Lovasz local lemma and critical exponents",
  "authors": [
    "Andrey Rumyantsev"
  ],
  "journal": "Andrey Yu. Rumyantsev, Kolmogorov Complexity, Lov\\'asz Local Lemma and Critical Exponents, Springer, Lecture Notes in Computer Science, Volume 4649 / 2007, CSR 2007, pp. 349--355",
  "categories": [
    "math.CO",
    "cs.DS"
  ],
  "abstract": "D. Krieger and J. Shallit have proved that every real number greater than 1 is a critical exponent of some sequence. We show how this result can be derived from some general statements about sequences whose subsequences have (almost) maximal Kolmogorov complexity. In this way one can also construct a sequence that has no \"approximate\" fractional powers with exponent that exceeds a given value.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2010-09-25T08:44:10.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "lovasz local lemma",
      "critical exponent",
      "maximal kolmogorov complexity",
      "real number greater",
      "general statements"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1009.4995R"
    }
  }
}