Shotgun reconstruction in the hypercube
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 equiv...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Wiley
2021
|
| _version_ | 1797079181493796864 |
|---|---|
| author | Przykucki, M Roberts, A Scott, AD |
| author_facet | Przykucki, M Roberts, A Scott, AD |
| author_sort | Przykucki, M |
| collection | OXFORD |
| description | 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.
|
| first_indexed | 2024-03-07T00:42:05Z |
| format | Journal article |
| id | oxford-uuid:836359c9-f213-425b-9338-ace19eee54a1 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T00:42:05Z |
| publishDate | 2021 |
| publisher | Wiley |
| record_format | dspace |
| spelling | oxford-uuid:836359c9-f213-425b-9338-ace19eee54a12022-03-26T21:43:52ZShotgun reconstruction in the hypercubeJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:836359c9-f213-425b-9338-ace19eee54a1EnglishSymplectic ElementsWiley2021Przykucki, MRoberts, AScott, ADMossel 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. |
| spellingShingle | Przykucki, M Roberts, A Scott, AD Shotgun reconstruction in the hypercube |
| title | Shotgun reconstruction in the hypercube |
| title_full | Shotgun reconstruction in the hypercube |
| title_fullStr | Shotgun reconstruction in the hypercube |
| title_full_unstemmed | Shotgun reconstruction in the hypercube |
| title_short | Shotgun reconstruction in the hypercube |
| title_sort | shotgun reconstruction in the hypercube |
| work_keys_str_mv | AT przykuckim shotgunreconstructioninthehypercube AT robertsa shotgunreconstructioninthehypercube AT scottad shotgunreconstructioninthehypercube |