Journal article
Shotgun reconstruction in the hypercube
- Abstract:
- Mossel and Ross raised the question of when a random colouring of a graph can be reconstructed from local information, namely the colourings (with multiplicity) of balls of given radius. In this paper, we are concerned with random 2-colourings of the vertices of the n-dimensional hypercube, or equivalently random Boolean functions. In the worst case, balls of diameter Ω(n) are required to reconstruct. However, the situation for random colourings is dramatically different: we show that almost every 2-colouring can be reconstructed from the multiset of colourings of balls of radius 2. Furthermore, we show that for q ≥ n 2+∈ , almost every q-colouring can be reconstructed from the multiset of colourings of 1-balls.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 800.1KB, Terms of use)
-
- Publisher copy:
- 10.1002/rsa.21028
Authors
- Publisher:
- Wiley
- Journal:
- Random Structures and Algorithms More from this journal
- Volume:
- 60
- Issue:
- 1
- Pages:
- 117-150
- Publication date:
- 2021-06-25
- Acceptance date:
- 2021-02-16
- DOI:
- EISSN:
-
1098-2418
- ISSN:
-
1042-9832
- Language:
-
English
- Keywords:
- Pubs id:
-
1069815
- Local pid:
-
pubs:1069815
- Deposit date:
-
2021-05-16
- ARK identifier:
Terms of use
- Copyright holder:
- Przykucki et al.
- Copyright date:
- 2021
- Rights statement:
- © 2021 The Authors. Random Structures & Algorithms published by Wiley Periodicals LLC. This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record