  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_k$ of length at most $n$, the task is to
determine the length of the longest common subsequence of $X_1,\dots,X_k$ that
is also strictly increasing. Especially for the case of $k=2$ (called LCIS for
short), several algorithms have been proposed that require quadratic time in
the worst case.
  Assuming the Strong Exponential Time Hypothesis (SETH), we prove a tight
lower bound, specifically, that no algorithm solves LCIS in (strongly)
subquadratic time. Interestingly, the proof makes no use of normalization
tricks common to hardness proofs for similar problems such as LCS. We further
strengthen this lower bound (1) to rule out $O((nL)^{1-\varepsilon})$ time
algorithms for LCIS, where $L$ denotes the solution size, (2) to rule out
$O(n^{k-\varepsilon})$ time algorithms for $k$-LCIS, and (3) to follow already
from weaker variants of SETH. We obtain the same conditional lower bounds for
the related Longest Common Weakly Increasing Subsequence problem.
