Improved Lower Bounds on the Expected Length of Longest Common Subsequences
<|reference_start|>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 $\sigma$ converges to some constant that depends only on $d$ and $\sigma$. 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 $\sigma$ and $d$, with the best lower and upper bounds for the most studied case, $\sigma=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 $\sigma=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.<|reference_end|>
@article{heineman2024improved,
    title={Improved Lower Bounds on the Expected Length of Longest Common
  Subsequences},
    author={George T. Heineman, Chase Miller, Daniel Reichman, Andrew Salls,
  G'abor S'ark"ozy, Duncan Soiffer},
    journal={arXiv preprint arXiv:2407.10925},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.10925},
    primaryClass={cs.DS}
}