{
  "id": "2009.03296",
  "version": "v1",
  "published": "2020-09-07T17:56:08.000Z",
  "updated": "2020-09-07T17:56:08.000Z",
  "title": "New Upper Bounds for Trace Reconstruction",
  "authors": [
    "Zachary Chase"
  ],
  "comment": "18 pages",
  "categories": [
    "math.PR",
    "cs.IT",
    "math.CO",
    "math.IT"
  ],
  "abstract": "We improve the upper bound on worst case trace reconstruction from $\\exp(O(n^{1/3}))$ to $\\exp(\\widetilde{O}(n^{1/5}))$ for any deletion probability $q \\le \\frac{1}{2}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-09-07T17:56:08.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "upper bound",
      "worst case trace reconstruction",
      "deletion probability"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}