{
  "id": "1808.02336",
  "version": "v1",
  "published": "2018-08-04T05:45:19.000Z",
  "updated": "2018-08-04T05:45:19.000Z",
  "title": "Lower bounds for trace reconstruction",
  "authors": [
    "Nina Holden",
    "Russell Lyons"
  ],
  "comment": "22 pages, 3 figures",
  "categories": [
    "math.PR",
    "cs.CC",
    "cs.IT",
    "math.IT",
    "math.ST",
    "stat.TH"
  ],
  "abstract": "In the trace reconstruction problem, an unknown bit string ${\\bf x}\\in\\{0,1\\}^n$ is sent through a deletion channel where each bit is deleted independently with some probability $q\\in(0,1)$, yielding a contracted string $\\widetilde{\\bf x}$. How many i.i.d. samples of $\\widetilde{\\bf x}$ are needed to reconstruct ${\\bf x}$ with high probability? We prove that there exist ${\\bf x},{\\bf y}\\in\\{0,1 \\}^n$ such that we need at least $c\\, n^{5/4}/\\sqrt{\\log n}$ traces to distinguish between ${\\bf x}$ and ${\\bf y}$ for some absolute constant $c$, improving the previous lower bound of $c\\,n$. Furthermore, our result improves the previously known lower bound for reconstruction of random strings from $c \\log^2 n$ to $c \\log^{9/4}n/\\sqrt{\\log \\log n} $.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-08-04T05:45:19.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "62C20",
      "68Q25",
      "68W32",
      "68W40",
      "68Q87",
      "60K30"
    ],
    "keywords": [
      "lower bound",
      "trace reconstruction problem",
      "absolute constant",
      "high probability",
      "random strings"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 22,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}