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 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 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
 host publication
 Theory and Applications of Models of Computation  14th Annual Conference, TAMC 2017, Proceedings
 series title
 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
 volume
 10185 LNCS
 pages
 13 pages
 publisher
 Springer
 conference name
 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017
 conference location
 Bern, Switzerland
 conference dates
 20170420  20170422
 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
 20200112 23:43:49
@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}, language = {eng}, pages = {412424}, publisher = {Springer}, series = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)}, title = {Bounds for semidisjoint bilinear forms in a unitcost computational model}, volume = {10185 LNCS}, year = {2017}, }