Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems
<|reference_start|>Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems: 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.<|reference_end|>
@article{hu2024non-boolean,
    title={Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic
  Problems},
    author={Bingbing Hu and Adam Polak},
    journal={arXiv preprint arXiv:2409.15970},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.15970},
    primaryClass={cs.CC cs.DS}
}