Reconstructing random pictures
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916585870983168 |
|---|---|
| author | Narayanan, Bhargav Yap, Corrine |
| author_facet | Narayanan, Bhargav Yap, Corrine |
| contents | Given a random binary picture $P_n$ of size $n$, i.e., an $n\times n$ grid filled with zeros and ones uniformly at random, when is it possible to reconstruct $P_n$ from its $k$-deck, i.e., the multiset of all its $k\times k$ subgrids? We demonstrate ``two-point concentration'' for the reconstruction threshold by showing that there is an integer $k_c(n) \sim (2 \log n)^{1/2}$ such that if $k > k_c$, then $P_n$ is reconstructible from its $k$-deck with high probability, and if $k < k_c$, then with high probability, it is impossible to reconstruct $P_n$ from its $k$-deck. The proof of this result uses a combination of interface-exploration arguments and entropic arguments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2210_09410 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Reconstructing random pictures Narayanan, Bhargav Yap, Corrine Combinatorics Probability 60C05 (Primary), 60K35, 68R15 (Secondary) Given a random binary picture $P_n$ of size $n$, i.e., an $n\times n$ grid filled with zeros and ones uniformly at random, when is it possible to reconstruct $P_n$ from its $k$-deck, i.e., the multiset of all its $k\times k$ subgrids? We demonstrate ``two-point concentration'' for the reconstruction threshold by showing that there is an integer $k_c(n) \sim (2 \log n)^{1/2}$ such that if $k > k_c$, then $P_n$ is reconstructible from its $k$-deck with high probability, and if $k < k_c$, then with high probability, it is impossible to reconstruct $P_n$ from its $k$-deck. The proof of this result uses a combination of interface-exploration arguments and entropic arguments. |
| title | Reconstructing random pictures |
| topic | Combinatorics Probability 60C05 (Primary), 60K35, 68R15 (Secondary) |
| url | https://arxiv.org/abs/2210.09410 |