Bounds for semi-disjoint bilinear forms in a unit-cost 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.412-424- Abstract
We study the complexity of the so called semi-disjoint bilin-ear forms over different semi-rings, in particular the n-dimensional vector convolution and n × n matrix product. We consider a powerful unit-cost computational model over the ring of integers allowing for several addi-tional operations and generation of large integers. We show the following dichotomy for such a powerful model: while almost all arithmetic semi-disjoint 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 non-trivial lower bounds for these three... (More)
We study the complexity of the so called semi-disjoint bilin-ear forms over different semi-rings, in particular the n-dimensional vector convolution and n × n matrix product. We consider a powerful unit-cost computational model over the ring of integers allowing for several addi-tional operations and generation of large integers. We show the following dichotomy for such a powerful model: while almost all arithmetic semi-disjoint 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 non-trivial 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, Semi-disjoint bilinear form, Semi-ring, Time complexity, Unit-cost ram, Vector convolu-tion
- 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
- 2017-04-20 - 2017-04-22
- external identifiers
-
- scopus:85018441953
- ISSN
- 16113349
- 03029743
- ISBN
- 9783319559100
- language
- English
- LU publication?
- yes
- id
- 22cfe299-df40-428c-ac33-75fb1a13acb8
- date added to LUP
- 2017-05-23 09:04:06
- date last changed
- 2025-01-07 13:55:52
@inproceedings{22cfe299-df40-428c-ac33-75fb1a13acb8, abstract = {{<p>We study the complexity of the so called semi-disjoint bilin-ear forms over different semi-rings, in particular the n-dimensional vector convolution and n × n matrix product. We consider a powerful unit-cost computational model over the ring of integers allowing for several addi-tional operations and generation of large integers. We show the following dichotomy for such a powerful model: while almost all arithmetic semi-disjoint 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 non-trivial 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}}, keywords = {{Circuit complexity; Distance product; Matrix multiplication; Semi-disjoint bilinear form; Semi-ring; Time complexity; Unit-cost ram; Vector convolu-tion}}, language = {{eng}}, pages = {{412--424}}, publisher = {{Springer}}, series = {{Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)}}, title = {{Bounds for semi-disjoint bilinear forms in a unit-cost computational model}}, volume = {{10185 LNCS}}, year = {{2017}}, }