Papers › Improved Lower Bounds on the Expected Length of Longest Common Subsequences
Improved Lower Bounds on the Expected Length of Longest Common Subsequences
George T. Heineman, Chase Miller, Daniel Reichman, Andrew Salls, Gábor Sárközy, Duncan Soiffer
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections