Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911132439019520 |
|---|---|
| author | Hu, Bingbing Polak, Adam |
| author_facet | Hu, Bingbing Polak, Adam |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_15970 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems Hu, Bingbing Polak, Adam Computational Complexity Data Structures and Algorithms 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. |
| title | Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2409.15970 |