An Algorithm to Recover Shredded Random Matrices
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911850120085504 |
|---|---|
| author | Atamanchuk, Caelan Devroye, Luc Vicenzo, Massimo |
| author_facet | Atamanchuk, Caelan Devroye, Luc Vicenzo, Massimo |
| contents | Given some binary matrix $M$, suppose we are presented with the collection of its rows and columns in independent arbitrary orderings. From this information, are we able to recover the unique original orderings and matrix? We present an algorithm that identifies whether there is a unique ordering associated with a set of rows and columns, and outputs either the unique correct orderings for the rows and columns or the full collection of all valid orderings and valid matrices. We show that there is a constant $c > 0$ such that the algorithm terminates in $O(n^2)$ time with high probability and in expectation for random $n \times n$ binary matrices with i.i.d.\ Bernoulli $(p)$ entries $(m_{ij})_{ij=1}^n$ such that $\frac{c\log^2(n)}{n(\log\log(n))^2} \leq p \leq \frac{1}{2}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_16715 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | An Algorithm to Recover Shredded Random Matrices Atamanchuk, Caelan Devroye, Luc Vicenzo, Massimo Probability Discrete Mathematics Data Structures and Algorithms Combinatorics 60C05 (Primary) 68Q25 (Secondary) Given some binary matrix $M$, suppose we are presented with the collection of its rows and columns in independent arbitrary orderings. From this information, are we able to recover the unique original orderings and matrix? We present an algorithm that identifies whether there is a unique ordering associated with a set of rows and columns, and outputs either the unique correct orderings for the rows and columns or the full collection of all valid orderings and valid matrices. We show that there is a constant $c > 0$ such that the algorithm terminates in $O(n^2)$ time with high probability and in expectation for random $n \times n$ binary matrices with i.i.d.\ Bernoulli $(p)$ entries $(m_{ij})_{ij=1}^n$ such that $\frac{c\log^2(n)}{n(\log\log(n))^2} \leq p \leq \frac{1}{2}$. |
| title | An Algorithm to Recover Shredded Random Matrices |
| topic | Probability Discrete Mathematics Data Structures and Algorithms Combinatorics 60C05 (Primary) 68Q25 (Secondary) |
| url | https://arxiv.org/abs/2310.16715 |