# Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems

arXiv: https://arxiv.org/abs/2409.15970 · HTML: https://mlsanity.com/paper/2409.15970/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Sep 2024.

## Built on by (most cited first, 1 of 1)

- [The Structural Complexity of Matrix-Vector Multiplication](https://mlsanity.com/paper/2502.21240/) (2025)

## Abstract (arXiv)

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. Somewhat surprisingly, we show that they are actually equivalent to it. This establishes the first such fine-grained equivalence class for dynamic problems.