Tight Conditional Lower Bounds for Longest Common Increasing Subsequence

Lech Duraj, Marvin Künnemann, Adam Polak

We consider the canonical generalization of the well-studied Longest Increasing Subsequence problem to multiple sequences, called $k$-LCIS: Given $k$ integer sequences $X_1,\dots,X…