- Series
- ACO Colloquium
- Time
- Thursday, March 3, 2011 - 4:30pm for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Alon Orlitsky – Professor, UCSD – alon@ucsd.edu
- Organizer
- Prasad Tetali
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.