{
  "id": "1701.07667",
  "version": "v1",
  "published": "2017-01-26T12:06:14.000Z",
  "updated": "2017-01-26T12:06:14.000Z",
  "title": "Indistinguishable sceneries on the Boolean hypercube",
  "authors": [
    "Renan Gross",
    "Uri Grupel"
  ],
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "We show that the scenery reconstruction problem on the Boolean hypercube is in general impossible. This is done by using locally biased functions, in which every vertex has a constant fraction of neighbors colored by $1$, and locally stable functions, in which every vertex has a constant fraction of neighbors colored by its own color. Our methods are constructive, and also give super-polynomial lower bounds on the number of locally biased and locally stable functions. We further show similar results for $\\mathbb{Z}^n$ and other graphs, and offer several follow-up questions.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-01-26T12:06:14.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "boolean hypercube",
      "indistinguishable sceneries",
      "constant fraction",
      "locally stable functions",
      "super-polynomial lower bounds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}