Improved bounds for rectangular monotone Min-Plus Product

A recent breakthrough in fine-grained complexity is the publication by Chi et al. (STOC'22) of anÕ(n^{3 + omega}/2) time algorithm to compute Monotone Min-Plus Product between two square matrices of dimensions n x n and polynomial bounded values. Here omega denotes the exponent of the fast matrix multiplication. As several applications were reduced to Monotone Min-Plus Product, this result leads to improved bounds for those applications as well. However the reductions use rectangular matrices and even though Chi et al.’s algorithm seems applicable for the rectangular case, the generalization is not straightforward.
  Chiet al present their algorithm in two steps: they first show a basic algorithm and then further improve the running time via recursion. In my presentation I will present a generalization of the basic algorithm to compute the Monotone Min-Plus Product between rectangular matrices. The generalization of the recursive algorithm is presented in detail in my paper, as well as the computation leading to the improved bounds for M-bounded SSRP, Batch Range Mode, k-Dyck Edit Distance and 2-approximation of APSP.