# Faster Min-Plus Product for Monotone Instances

arXiv: https://arxiv.org/abs/2204.04500 · HTML: https://mlsanity.com/paper/2204.04500/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Apr 2022.

## Built on by (most cited first, 1 of 1)

- [Regularized Robustly Reliable Learners and Instance Targeted Attacks](https://mlsanity.com/paper/2410.10572/) (2024)

## Abstract (arXiv)

In this paper, we show that the time complexity of monotone min-plus product of two n× n matrices is tildeO(n(3+ω)/2)=tildeO(n2.687), where ω < 2.373 is the fast matrix multiplication exponent [Alman and Vassilevska Williams 2021]. That is, when A is an arbitrary integer matrix and B is either row-monotone or column-monotone with integer elements bounded by O(n), computing the min-plus product C where Ci,j=minkAi,k+Bk,j takes tildeO(n(3+ω)/2) time, which greatly improves the previous time bound of tildeO(n(12+ω)/5)=tildeO(n2.875) [Gu, Polak, Vassilevska Williams and Xu 2021]. Then by simple reductions, this means the following problems also have tildeO(n(3+ω)/2) time algorithms: (1) A and B are both bounded-difference, that is, the difference between any two adjacent entries is a constant. The previous results give time complexities of tildeO(n2.824) [Bringmann, Grandoni, Saha and Vassilevska Williams 2016] and tildeO(n2.779) [Chi, Duan and Xie 2022]. (2) A is arbitrary and the columns or rows of B are bounded-difference. Previous result gives time complexity of tildeO(n2.922) [Bringmann, Grandoni, Saha and Vassilevska Williams 2016]. (3) The problems reducible to these problems, such as language edit distance, RNA-folding, scored parsing problem on BD grammars. [Bringmann, Grandoni, Saha and Vassilevska Williams 2016]. Finally, we also consider the problem of min-plus convolution between two integral sequences which are monotone and bounded by O(n), and achieve a running time upper bound of tildeO(n1.5). Previously, this task requires running time tildeO(n^(9+√177)/12) = O(n1.859) [Chan and Lewenstein 2015].