Bounds for semidisjoint bilinear forms in a unitcost computational model
(2017) 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017 In Theory and Applications of Models of Computation  14th Annual Conference, TAMC 2017, Proceedings 10185 LNCS. p.412424 Abstract
We study the complexity of the so called semidisjoint bilinear forms over different semirings, in particular the ndimensional vector convolution and n × n matrix product. We consider a powerful unitcost 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 semidisjoint 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 nontrivial lower bounds for these three... (More)
We study the complexity of the so called semidisjoint bilinear forms over different semirings, in particular the ndimensional vector convolution and n × n matrix product. We consider a powerful unitcost 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 semidisjoint 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 nontrivial 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.
(Less)
 author
 Lingas, Andrzej ^{LU} ; Persson, Mia ^{LU} and Sledneu, Dzmitry ^{LU}
 organization
 publishing date
 2017
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 keywords
 Circuit complexity, Distance product, Matrix multiplication, Semidisjoint bilinear form, Semiring, Time complexity, Unitcost ram, Vector convolution
 in
 Theory and Applications of Models of Computation  14th Annual Conference, TAMC 2017, Proceedings
 volume
 10185 LNCS
 pages
 13 pages
 publisher
 Springer Verlag
 conference name
 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017
 external identifiers

 scopus:85018441953
 ISSN
 16113349
 03029743
 ISBN
 9783319559100
 language
 English
 LU publication?
 yes
 id
 22cfe299df40428cac3375fb1a13acb8
 date added to LUP
 20170523 09:04:06
 date last changed
 20180107 12:04:43
@inproceedings{22cfe299df40428cac3375fb1a13acb8, abstract = {<p>We study the complexity of the so called semidisjoint bilinear forms over different semirings, in particular the ndimensional vector convolution and n × n matrix product. We consider a powerful unitcost 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 semidisjoint 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 nontrivial 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.</p>}, author = {Lingas, Andrzej and Persson, Mia and Sledneu, Dzmitry}, booktitle = {Theory and Applications of Models of Computation  14th Annual Conference, TAMC 2017, Proceedings}, isbn = {9783319559100}, issn = {16113349}, keyword = {Circuit complexity,Distance product,Matrix multiplication,Semidisjoint bilinear form,Semiring,Time complexity,Unitcost ram,Vector convolution}, language = {eng}, pages = {412424}, publisher = {Springer Verlag}, title = {Bounds for semidisjoint bilinear forms in a unitcost computational model}, volume = {10185 LNCS}, year = {2017}, }