Elchanan Mossel: Corruption Detection and Shotgun Assembly of Networks

Abstract: I will discuss two algorithmic problems on networks. The first problem is the classical and well studied problem of identifying faulty nodes in a network given reports of their neighbors. This problem has been studied since the 1960s as a problem of diagnosable systems, as a Byzantine computing problem and as an intrusion detection problem. I will present the first results (with Alon and Pemantle) that analyze the problem in the case of bounded degree graphs. In the second part of the talk  (based on joint works with Nathan Ross and Nike Sun) I will present a new problem: the graph shotgun problem which generalizes the DNA shotgun problem. A number of open problems will be presented.