Asymptotics in Sequence Comparison

Department: 
MATH
Course Number: 
8803 HOU
Hours - Lecture: 
3
Hours - Lab: 
0
Hours - Recitation: 
0
Hours - Total Credit: 
3
Typical Scheduling: 
no regular schedule

Special Topics course offered in Spring 2017 by Christian Houdre.

Prerequisites: 

Strong knowledge of Probability Theory at the level of MATH 7244

Course Text: 

TBA

Topic Outline: 

The main goal of this course is to present very recent results on the asymptotic behavior (mean, variance, limiting law) of the length of various longest subsequences in random words, culminating with the proof of the recent breakthrough results on the limiting law of the length of the longest common subsequences in two or more random words.  

Outline:

1.Length of the Longest Increasing subsequences in a Random Word:  Limiting laws as Brownian Functionals 
2. Young Diagrams, Brownian Functionals and Spectra of Gaussian Random matrices 
3. A Non-Central Limit Theorem for the Length of the Longest Common and Increasing Subsequences in Random Words
4. A Central Limit Theorem for the Length of the Longest Common  Subsequences in Random Words 
5. Some Open Problems and Some Conjectures