An algorithm to recover shredded random matrices
From MaRDI portal
Publication:6622734
DOI10.1137/23m1615784MaRDI QIDQ6622734
Luc P. Devroye, Caelan Atamanchuk, Massimo Vicenzo
Publication date: 22 October 2024
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
analysis of algorithmscombinatorial probabilitygraph reconstructionexpected complexitymatrix reconstruction
Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Combinatorial probability (60C05) Random matrices (algebraic aspects) (15B52) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A congruence theorem for trees
- On a new digraph reconstruction conjecture
- The cycle structure of random permutations
- Graph reconstruction -- some new developments
- Shotgun assembly of Erdős-Rényi random graphs
- Almost every graph has reconstruction number three
- The graph reconstruction number
- On the Complexity of Canonical Labeling of Strongly Regular Graphs
- Random Graph Isomorphism
- A Linear Threshold for Uniqueness of Solutions to Random Jigsaw Puzzles
- Information Theory of DNA Shotgun Sequencing
- Unique reconstruction threshold for random jigsaw puzzles
- Shotgun reconstruction in the hypercube
This page was built for publication: An algorithm to recover shredded random matrices