An algorithm to recover shredded random matrices

DOI10.1137/23M1615784MaRDI QIDQ6622734zbMATH OpenFDO

Authors Caelan Atamanchuk, Luc Devroye, Massimo Vicenzo

Publication date 22 October 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/23M1615784

zbMATH Keywords

analysis of algorithmscombinatorial probabilitygraph reconstructionexpected complexitymatrix reconstruction

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Combinatorics in computer science (68R05) Analysis of algorithms (68W40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Combinatorial probability (60C05)

Recommendations

• Matrix recovery from permutations
• scientific article; zbMATH DE number 809139
• Testing of random matrices
• Reconstruction of matrices from submatrices

Cites work

• scientific article; zbMATH DE number 3141308 (Why is no real title available?)
• scientific article; zbMATH DE number 3458693 (Why is no real title available?)
• scientific article; zbMATH DE number 3544095 (Why is no real title available?)
• A Linear Threshold for Uniqueness of Solutions to Random Jigsaw Puzzles
• A congruence theorem for trees
• Almost every graph has reconstruction number three
• Graph reconstruction -- some new developments
• Information Theory of DNA Shotgun Sequencing
• On a new digraph reconstruction conjecture
• On the Complexity of Canonical Labeling of Strongly Regular Graphs
• Random Graph Isomorphism
• Shotgun assembly of Erdős-Rényi random graphs
• Shotgun reconstruction in the hypercube
• The cycle structure of random permutations
• The graph reconstruction number
• Unique reconstruction threshold for random jigsaw puzzles

Cited in

(1)

• Reconstruction of shredded random matrices

This page was built for publication: An algorithm to recover shredded random matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6622734)