An Optimal MPC Algorithm for Subunit-Monge Matrix Multiplication, with Applications to LIS
<|reference_start|>An Optimal MPC Algorithm for Subunit-Monge Matrix Multiplication, with Applications to LIS: 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 a $O(\log n)$-round fully-scalable massively parallel algorithm for solving the exact longest increasing subsequence (LIS) problem. For a fully-scalable MPC regime, this result substantially improves the previously known algorithm of $O(\log^4 n)$-round complexity, and matches the best algorithm for computing the $(1+\epsilon)$-approximation of LIS.<|reference_end|>
@article{koo2024an,
    title={An Optimal MPC Algorithm for Subunit-Monge Matrix Multiplication, with
  Applications to LIS},
    author={Jaehyun Koo},
    journal={arXiv preprint arXiv:2404.13486},
    year={2024},
    doi={10.1145/3626183.3659974},
    archivePrefix={arXiv},
    eprint={2404.13486},
    primaryClass={cs.DS}
}