Reconstruction of shredded random matrices
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910293209120768 |
|---|---|
| author | Balister, Paul Kronenberg, Gal Scott, Alex Tamitegama, Youri |
| author_facet | Balister, Paul Kronenberg, Gal Scott, Alex Tamitegama, Youri |
| contents | A matrix is given in ``shredded'' form if we are presented with the multiset of rows and the multiset of columns, but not told which row is which or which column is which. The matrix is reconstructible if it is uniquely determined by this information. Let $M$ be a random binary $n\times n$ matrix, where each entry independently is $1$ with probability $p=p(n)\le\frac12$. Atamanchuk, Devroye and Vicenzo introduced the problem and showed that $M$ is reconstructible with high probability for $p\ge (2+\varepsilon)\frac{1}{n}\log n$. Here we find that the sharp threshold for reconstructibility is at $p\sim\frac{1}{2n}\log n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_05058 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Reconstruction of shredded random matrices Balister, Paul Kronenberg, Gal Scott, Alex Tamitegama, Youri Combinatorics A matrix is given in ``shredded'' form if we are presented with the multiset of rows and the multiset of columns, but not told which row is which or which column is which. The matrix is reconstructible if it is uniquely determined by this information. Let $M$ be a random binary $n\times n$ matrix, where each entry independently is $1$ with probability $p=p(n)\le\frac12$. Atamanchuk, Devroye and Vicenzo introduced the problem and showed that $M$ is reconstructible with high probability for $p\ge (2+\varepsilon)\frac{1}{n}\log n$. Here we find that the sharp threshold for reconstructibility is at $p\sim\frac{1}{2n}\log n$. |
| title | Reconstruction of shredded random matrices |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2401.05058 |