Advanced

Bounds for semi-disjoint bilinear forms in a unit-cost computational model

Lingas, Andrzej LU ; Persson, Mia LU and Sledneu, Dzmitry LU (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.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)
Please use this url to cite or link to this publication:
author
organization
publishing date
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
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
22cfe299-df40-428c-ac33-75fb1a13acb8
date added to LUP
2017-05-23 09:04:06
date last changed
2018-01-07 12:04:43
@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},
  keyword      = {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 Verlag},
  title        = {Bounds for semi-disjoint bilinear forms in a unit-cost computational model},
  volume       = {10185 LNCS},
  year         = {2017},
}