EUVIMEDEUVIMED entdecken
Crossref

Reconstruction of shredded random matrices

Paul Balister, Gal Kronenberg, Alex Scott, Youri Tamitegama

Journal of Combinatorial Theory, Series B · 2026-07 · 179 · 315-334

DOI: 10.1016/j.jctb.2026.04.003 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Combinatorial Theory, Series B, 2026-07. Verfasst von Paul Balister und 3 weiteren Autor:innen. Die Arbeit nennt 23 Literaturangaben. Gefördert von: Royal Commission for the Exhibition of 1851, Engineering and Physical Sciences Research Council.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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$.

Förderung

  • Royal Commission for the Exhibition of 1851
  • Engineering and Physical Sciences Research Council

Zitieren

APA

Balister, P., Kronenberg, G., Scott, A., & Tamitegama, Y. (2026). Reconstruction of shredded random matrices. Journal of Combinatorial Theory, Series B, 179, 315-334. https://doi.org/10.1016/j.jctb.2026.04.003

Vancouver

Balister P, Kronenberg G, Scott A, Tamitegama Y. Reconstruction of shredded random matrices. Journal of Combinatorial Theory, Series B. 2026;179:315-334. doi:10.1016/j.jctb.2026.04.003

BibTeX
@article{Balister2026,
  author = {Balister, Paul and Kronenberg, Gal and Scott, Alex and Tamitegama, Youri},
  title = {Reconstruction of shredded random matrices},
  journal = {Journal of Combinatorial Theory, Series B},
  year = {2026},
  volume = {179},
  pages = {315--334},
  doi = {10.1016/j.jctb.2026.04.003}
}
Kostenlos starten →