Carl Miller–The Longest Common Subsequence Problem

Let X_1, X_2, …, X_n and Y_1, Y_2, …, Y_n be two independent random binary sequences, and let c_n be the length of the longest subsequence which is common to both of them. The longest common subsequence problem asks for the limit of E(c_n)/n as n goes to infinity. The value of this constant is not known, and the best proved approximations are weak. I'll discuss this problem and then show how it is connected to a question about "random growth" on a 2-dimensional lattice. This connection suggests a method for approaching the problem.