An Optimal MPC Algorithm for Subunit-Monge Matrix Multiplication, with Applications to LIS

Jaehyun Koo

We present an $O(1)$-round fully-scalable deterministic massively parallel algorithm for computing the min-plus matrix multiplication of unit-Monge matrices. We use this to derive…