Bounds for semi-disjoint bilinear forms in a unit-cost computational model
We study the complexity of the so called semi-disjoint bilin-ear forms over different semi-rings, in particular the n-dimensional vector convolution and n × n matrix product. We consider a powerful unit-cost computational model over the ring of integers allowing for several addi-tional operations and generation of large integers. We show the following dichotomy for such a powerful model: while alm