2026-09-08T02:22:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26508 2026-09-05T19:46:09Z ddc:004 open_access

Deterministic Monotone Min-Plus Product and Convolution Jin, Ce Park, Jaewoo Saha, Barna Xu, Yinzhan Min-plus product min-plus convolution monotone matrices fine-grained complexity deterministic algorithms The Monotone Min-Plus Product problem is a useful primitive that has seen many algorithmic applications over the past decade. It also generalizes various other structured Min-Plus products studied in the literature, such as Bounded Difference Min-Plus Product and Bounded Integer Min-Plus Product. In this problem, we are given two n× n integer matrices A and B, where each row of B is a monotone non-decreasing sequence of integers from {1,…,n}, and the goal is to compute their Min-Plus product, defined as the n× 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)} = 𝒪(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 running time n^{(ω+3)/2 + o(1)} = 𝒪(n^2.686) as its randomized counterpart, improving upon the previous deterministic bound 𝒪(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 𝒪̃(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ce Jin and Jaewoo Park and Barna Saha and Yinzhan Xu 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.119 urn:nbn:de:0030-drops-265085 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.119 eng https://creativecommons.org/licenses/by/4.0/legalcode