Improved Lower Bounds on the Expected Length of Longest Common Subsequences

It has been proven that, when normalized by n, the expected length of a longest common subsequence of d random strings of length n over an alphabet of size σ converges to some constant that depends only on d and σ. These values are known as the Chv\'{a}tal-Sankoff constants, and determining their exact values is a well-known open problem. Upper and lower bounds are known for some combinations of σ and d, with the best lower and upper bounds for the most studied case, σ=2, d=2, at $0.788071$ and $0.826280$, respectively. Building off previous algorithms for lower-bounding the constants, we implement runtime optimizations, parallelization, and an efficient memory reading and writing scheme to obtain an improved lower bound of $0.792665992$ for σ=2, d=2. We additionally improve upon almost all previously reported lower bounds for the Chv\'{a}tal-Sankoff constants when either the size of alphabet, the number of strings, or both are larger than 2.