Subsequences in Words and Oscillations

Thursday, October 2, 2014 - 9:00am - 9:50am
Keller 3-180
Boris Bukh (Carnegie-Mellon University)
Given a set of t words made of 0's and 1's, we wish to find a pair of them with a long common subsequence. How long a subsequence can be guarantee? It turns out that this question naturally leads to a decomposition of words into pieces that oscillate at approximately the same frequency. I will explain the solution to the problem above, and to some of the related questions. Based on the the joint works with J. Ma and L. Zhou.
MSC Code: