Gal Kronenberg

Reconstructing shredded matrices

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. We say that a matrix is reconstructible if it is uniquely determined by this information. In this talk we will discuss reconstructing shredded random binary n×n matrices, where each entry independently is 1 with probability p. We will cover some history, new results, and related problems. In particular, we will present a sharp threshold for reconstructibility at p ∼ (log(n))/(2n).

This talk is based on a joint work with Paul Balister, Alex Scott, and Youri Tamitegama.