2 papers
cs.DS2024
An Optimal MPC Algorithm for Subunit-Monge Matrix Multiplication, with Applications to LIS
Jaehyun Koo
We present an -round fully-scalable deterministic massively parallel algorithm for computing the min-plus matrix multiplication of unit-Monge matrices. We use this to derive…
cs.DS2024
Anarchy in the APSP: Algorithm and Hardness for Incorrect Implementation of Floyd-Warshall
Jaehyun Koo
The celebrated Floyd-Warshall algorithm efficiently computes the all-pairs shortest path, and its simplicity made it a staple in computer science classes. Frequently, students disc…