2026-07-25T03:00:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24522 2025-12-16T14:00:19Z ddc:004 open_access

Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems Hu, Bingbing Polak, Adam Fine-grained complexity OMv hypothesis reductions equivalence class Most of the known tight lower bounds for dynamic problems are based on the Online Boolean Matrix-Vector Multiplication (OMv) Hypothesis, which is not as well studied and understood as some more popular hypotheses in fine-grained complexity. It would be desirable to base hardness of dynamic problems on a more believable hypothesis. We propose analogues of the OMv Hypothesis for variants of matrix multiplication that are known to be harder than Boolean product in the offline setting, namely: equality, dominance, min-witness, min-max, and bounded monotone min-plus products. These hypotheses are a priori weaker assumptions than the standard (Boolean) OMv Hypothesis and yet we show that they are actually equivalent to it. This establishes the first such fine-grained equivalence class for dynamic problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bingbing Hu and Adam Polak 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.54 urn:nbn:de:0030-drops-245228 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.54 eng https://creativecommons.org/licenses/by/4.0/legalcode