| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

6. Longest common subsequence


    1. Add remark

      Problem 6.1.

      Consider two independent random sequences (strings) of i.i.d. Bernoulli(0,1) variables, or more generally, i.i.d. variables taking values in a finite alphabet. The main question is to understand the typical size and the fluctuations of their longest common subsequence (LCS). Recent works have studied various regimes of this problem.


        • Add remark

          Problem 6.2.

          One central object of study is the almost-sure growth rate (or time constant) of the LCS as the string lengths grow. Determining this constant precisely remains an open problem in many cases. A potential approach would be to rephrase the LCS problem in the language close to LPP, and potentially use Busemann functions.

          In the special setting where one of the two sequences is purely periodic and the other is random, more progress has been made. In particular, the papers [MR4414706], [arXiv:2404.07285] relate the LCS problem to a version of the PushTASEP on the ring.

              Cite this as: AimPL: All roads to the KPZ universality class, available at http://aimpl.org/roadtokpz.