# Deterministic Monotone Min-Plus Product and Convolution

Preprint · Ce Jin, Jaewoo Park, Barna Saha, Yinzhan Xu

- Archive id: arxiv:2605.07150
- Published: 2026-05-08
- arXiv: https://arxiv.org/abs/2605.07150
- Source URL: https://arxiv.org/abs/2605.07150
- PDF: https://arxiv.org/pdf/2605.07150
- Provenance: arxiv

## Abstract

The Monotone Min-Plus Product problem is a useful primitive that has seen many algorithmic applications over the past decade. In this problem, we are given two $n\\times n$ integer matrices $A$ and $B$, where each row of $B$ is a monotone non-decreasing sequence of integers from $\\{1,\\dots,n\\}$, and the goal is to compute their Min-Plus product, defined as the $n\\times n$ matrix $C$ with $C\_{i,j} = \\min\_{k}\\{A\_{i,k} + B\_{k,j}\\}$. The fastest known algorithm for this task \[Chi, Duan, Xie, and Zhang, STOC'22\] runs in $n^{(ω+3)/2+o(1)} = O(n^{2.686})$ time, significantly improving over the brute-force cubic algorithm. However, its main disadvantage is that it requires randomization, which is then inherited by all downstream applications. Our main result is a deterministic algorithm for Monotone Min-Plus product with the same time complexity $n^{(ω+3)/2+o(1)} = O(n^{2.686})$ as its randomized counterpart, improving upon the previous deterministic bound $O(n^{2.875})$ \[Gu, Polak, Vassilevska Williams, and Xu, ICALP'21\]. Our derandomization also applies to previously studied extensions and variants (e.g., \[Dürr, IPL'23\]), including rectangular matrices, bounded range $\[n^μ\]$, and column-monotone matrices. As an immediate consequence, we derandomize state-of-the-art algorithms for multiple problems, including Language Edit Distance, RNA Folding, Optimum Stack Generation, unweighted Tree Edit Distance, Batched Range Mode, and Approximate All-Pairs Shortest Paths. Our techniques also yield a deterministic algorithm for the Monotone Min-Plus Convolution problem that runs in $n^{1.5+o(1)}$ time, nearly matching the best known randomized time complexity $\\widetilde{O}(n^{1.5})$ \[Chi, Duan, Xie, and Zhang, STOC'22\]. This algorithm can be used to derandomize state-of-the-art algorithms for Jumbled Indexing for binary strings and several variants of Knapsack.

_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.