Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model

摘要

We study the complexity of the so called semi-disjoint bilinear forms over different semi-rings, in particular the n-dimensional vector convolution and n x n matrix product. We consider a powerful unit-cost computational model over the ring of integers allowing for several additional operations and generation of large integers. We show the following dichotomy for such a powerful model: while almost all arithmetic semi-disjoint bilinear forms have the same asymptotic time complexity as that yielded by naive algorithms, matrix multiplication, the so called distance matrix product, and vector convolution can be solved in a linear number of steps. It follows in particular that in order to obtain a non-trivial lower bounds for these three basic problems one has to assume restrictions on the set of allowed operations and/or the size of used integers.