Journal article
Reconstruction of shredded random matrices
- Abstract:
- 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 × n matrix, where each entry independently is 1 with probability p = p(n)≤1/2. Atamanchuk, Devroye and Vicenzo introduced the problem and showed that M is reconstructible with high probability for p≥(2+ε)1/n log n. Here we find that the sharp threshold for reconstructibility is at p∼1/2n log n.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 238.7KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.jctb.2026.04.003
Authors
+ Engineering and Physical Sciences Research Council
More from this funder
- Funder identifier:
- https://ror.org/0439y7842
- Grant:
- EP/X013642/1
- Publisher:
- Elsevier
- Journal:
- Journal of Combinatorial Theory, Series B More from this journal
- Volume:
- 179
- Pages:
- 315-334
- Publication date:
- 2026-05-08
- Acceptance date:
- 2026-04-13
- DOI:
- EISSN:
-
1096-0902
- ISSN:
-
0095-8956
- Language:
-
English
- Keywords:
- Pubs id:
-
2418910
- Local pid:
-
pubs:2418910
- Source identifiers:
-
W4390810024
- Deposit date:
-
2026-05-12
- ARK identifier:
Terms of use
- Copyright holder:
- Elsevier Inc.
- Copyright date:
- 2026
- Rights statement:
- © 2026 Published by Elsevier Inc.
- Notes:
- The author accepted manuscript (AAM) of this paper has been made available under the University of Oxford's Open Access Publications Policy, and a CC BY public copyright licence has been applied.
- 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