  We consider the statistical seriation problem, where the statistician seeks
to recover a hidden ordering from a noisy observation of a permuted Robinson
matrix. In this paper, we tightly characterize the minimax rate for this
problem of matrix reordering when the Robinson matrix is bi-Lipschitz, and we
also provide a polynomial time algorithm achieving this rate; thereby answering
two open questions of [Giraud et al., 2021]. Our analysis further extends to
broader classes of similarity matrices.
