Loading Events
  • This event has passed.
Stochastics and Statistics Seminar

Shotgun Assembly of Graphs

December 2, 2016 @ 11:00 am

Elchanan Mossel (MIT)


We will present some results and some open problems related to shotgun assembly of graphs for random generating models.Shotgun assembly of graphs is the problem of recovering a random graph or a randomly labelled graphs from small pieces.
This problem generalizes the theoretically elegant and practically important problem of shotgun assembly of DNA sequences.
The general problem of shotgun assembly presents novel problems in random graphs, percolation, and random constraint satisfaction problems.
Based on joint works with Nathan Ross, with Nike Sun and with Charles Bordenave and Uri Feige.

MIT Statistics + Data Science Center
Massachusetts Institute of Technology
77 Massachusetts Avenue
Cambridge, MA 02139-4307