ECCC-Report TR14-039https://eccc.weizmann.ac.il/report/2014/039Comments and Revisions published for TR14-039en-usFri, 28 Mar 2014 15:04:51 +0300
Revision 1
| Vector convolution in O(n) steps and matrix multiplication in O(n^2) steps :-) |
Andrzej Lingas,
Dzmitry Sledneu
https://eccc.weizmann.ac.il/report/2014/039#revision1We 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.Fri, 28 Mar 2014 15:04:51 +0300https://eccc.weizmann.ac.il/report/2014/039#revision1
Paper TR14-039
| Vector convolution in O(n) steps and matrix multiplication in O(n^2) steps :-) |
Andrzej Lingas
https://eccc.weizmann.ac.il/report/2014/039We 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.Fri, 28 Mar 2014 14:49:58 +0300https://eccc.weizmann.ac.il/report/2014/039