__
Revision #1 to TR14-039 | 28th March 2014 15:04
__
#### Vector convolution in O(n) steps and matrix multiplication in O(n^2) steps :-)

**Abstract:**
We observe that if we allow for the use of

division and the floor function

besides multiplication, addition and

subtraction then we can

compute the arithmetic convolution

of two n-dimensional integer vectors in O(n) steps and

perform the arithmetic matrix multiplication

of two integer n times n matrices in O(n^2) steps.

Hence, any method for proving superlinear

(in the input size) lower bounds

for the aforementioned problems has to assume a more restricted

set of arithmetic operations and/or an upper bound on the size

of allowed integers.

**Changes to previous version:**
Keywords and the second author were missing in the previous version.

__
TR14-039 | 28th March 2014 09:37
__

#### Vector convolution in O(n) steps and matrix multiplication in O(n^2) steps :-)

**Abstract:**
We observe that if we allow for the use of

division and the floor function

besides multiplication, addition and

subtraction then we can

compute the arithmetic convolution

of two n-dimensional integer vectors in O(n) steps and

perform the arithmetic matrix multiplication

of two integer n times n matrices in O(n^2) steps.

Hence, any method for proving superlinear

(in the input size) lower bounds

for the aforementioned problems has to assume a more restricted

set of arithmetic operations and/or an upper bound on the size

of allowed integers.