Alon Orlitsky (ECE and CSE, UC San Diego)
Wednesday, 20.7.2011, 13:30
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.