Improved bounds for rectangular monotone min-plus product and applications

DOI10.1016/J.IPL.2023.106358OpenAlexW4313495455MaRDI QIDQ2681403

Anita Dürr

Publication date: 3 February 2023

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2208.02862

zbMATH Keywords

algorithmsfine-grained complexitymonotone min-plus product

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

On the hardness of computing the edit distance of shallow trees ⋮ Weighted edit distance computation: strings, trees, and Dyck

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clustered Integer 3SUM via Additive Combinatorics
• Faster Replacement Paths and Distance Sensitivity Oracles
• Powers of tensors and fast matrix multiplication
• Faster All-Pairs Shortest Paths via Circuit Complexity
• Subcubic Equivalences Between Path, Matrix, and Triangle Problems
• Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications
• Faster all-pairs shortest paths via circuit complexity
• Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can)

This page was built for publication: Improved bounds for rectangular monotone min-plus product and applications