{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,28]],"date-time":"2023-08-28T12:59:46Z","timestamp":1693227586595},"reference-count":10,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2018,6,5]],"date-time":"2018-06-05T00:00:00Z","timestamp":1528156800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>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 neighbours coloured by 1, and locally stable functions, in which every vertex has a constant fraction of neighbours coloured by its own colour. 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 \u2124<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup> and other graphs, and offer several follow-up questions.<\/jats:p>","DOI":"10.1017\/s0963548318000305","type":"journal-article","created":{"date-parts":[[2018,6,5]],"date-time":"2018-06-05T09:26:12Z","timestamp":1528190772000},"page":"46-60","source":"Crossref","is-referenced-by-count":2,"title":["Indistinguishable Sceneries on the Boolean Hypercube"],"prefix":"10.1017","volume":"28","author":[{"given":"RENAN","family":"GROSS","sequence":"first","affiliation":[]},{"given":"URI","family":"GRUPEL","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,6,5]]},"reference":[{"key":"S0963548318000305_ref4","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-17.1.75"},{"key":"S0963548318000305_ref8","volume-title":"Introduction to Coding Theory","author":"van Lint","year":"1998"},{"key":"S0963548318000305_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139924160"},{"key":"S0963548318000305_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(1999010)14:1<71::AID-RSA4>3.0.CO;2-9"},{"key":"S0963548318000305_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782"},{"key":"S0963548318000305_ref5","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.917692"},{"key":"S0963548318000305_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02787104"},{"key":"S0963548318000305_ref7","doi-asserted-by":"publisher","DOI":"10.1216\/RMJ-1975-5-2-199"},{"key":"S0963548318000305_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.spa.2014.03.012"},{"key":"S0963548318000305_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-4149(03)00085-1"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000305","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,12]],"date-time":"2019-04-12T16:24:09Z","timestamp":1555086249000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000305\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,5]]},"references-count":10,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["S0963548318000305"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000305","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6,5]]}}}