Tight dynamic problem lower bounds from generalized BMM and OMv

Popular fine-grained hypotheses have been successful in proving conditional lower bounds for many dynamic problems. Two of the most widely applicable hypotheses in this context are the combinatorial Boolean Matrix Multiplication (BMM) hypothesis and the closely-related Online Matrix Vector Multiplication (OMv) hypothesis. The main theme of this paper is using k-dimensional generalizations of these two hypotheses to prove new tight conditional lower bounds for dynamic problems.