String Reconstruction from Substring Compositions

Series: 
ACO Colloquium
Thursday, March 3, 2011 - 16:30
1 hour (actually 50 minutes)
Location: 
Skiles 006
,  
Professor, UCSD
,  
Organizer: 
Motivated by mass-spectrometry protein sequencing, we consider the simple problem of reconstructing a string from its substring compositions. Relating the question to the long-standing turnpike problem, polynomial factorization, and cyclotomic polynomials, we cleanly characterize the lengths of reconstructable strings and the structure of non-reconstructable ones. The talk is elementary and self contained and covers work with Jayadev Acharya, Hirakendu Das, Olgica Milenkovic, and Shengjun Pan.