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

Preprint · Jaehyun Koo

- Archive id: arxiv:2404.13486
- Published: 2024-04-20
- DOI: https://doi.org/10.1145/3626183.3659974
- arXiv: https://arxiv.org/abs/2404.13486
- Source URL: https://arxiv.org/abs/2404.13486
- PDF: https://arxiv.org/pdf/2404.13486
- Provenance: arxiv

## Abstract

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+ε)$-approximation of LIS.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.