An algorithm to recover shredded random matrices

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)

zbMATH Keywords

analysis of algorithmscombinatorial probabilitygraph reconstructionexpected complexitymatrix reconstruction

Mathematics Subject Classification ID

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