{
  "id": "1905.03031",
  "version": "v1",
  "published": "2019-05-08T12:28:01.000Z",
  "updated": "2019-05-08T12:28:01.000Z",
  "title": "New Lower Bounds for Trace Reconstruction",
  "authors": [
    "Zachary Chase"
  ],
  "comment": "18 pages",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "We improve the lower bound on worst case trace reconstruction from $\\Omega\\left(\\frac{n^{5/4}}{\\sqrt{\\log n}}\\right)$ to $\\Omega\\left(\\frac{n^{3/2}}{\\log^{16} n}\\right)$. As a consequence, we improve the lower bound on average case trace reconstruction from $\\Omega\\left(\\frac{\\log^{9/4}n}{\\sqrt{\\log\\log n}}\\right)$ to $\\Omega\\left(\\frac{\\log^{5/2}n}{(\\log\\log n)^{16}}\\right)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-05-08T12:28:01.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "lower bound",
      "average case trace reconstruction",
      "worst case trace reconstruction",
      "consequence"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}