Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR14-039 | 28th March 2014 15:04

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

RSS-Feed




Revision #1
Authors: Andrzej Lingas, Dzmitry Sledneu
Accepted on: 28th March 2014 15:04
Downloads: 1024
Keywords: 


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.


Paper:

TR14-039 | 28th March 2014 09:37

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





TR14-039
Authors: Andrzej Lingas
Publication: 28th March 2014 14:49
Downloads: 2333
Keywords: 


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.



ISSN 1433-8092 | Imprint