***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Alex Scott (U Oxford)

Thursday 8th February, 3:00 in Fine Hall 224.

Title: Reconstructing shredded random 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. The matrix is reconstructible if it is uniquely 
determined by this information. Let M be a random binary n × n matrix, 
where each entry independently is 1 with probability p = p(n) \le 1/2. 
Atamanchuk, Devroye and Vicenzo introduced the problem and showed that M 
is reconstructible with high probability for p > (2 + ε)(log n)/n. Here we 
find that the sharp threshold for reconstructibility is at (1/2)(log n)/n.

Joint work with Paul Balister, Gal Kronenberg and Youri Tamitegama


		----------------------------------


Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)