Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model

DSpace Repository

Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model

Details

Files for download

Find Full text There are no files associated with this item..

Overview of item record
Publication Paper in proceeding
Title Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model
Author Lingas, Andrzej ; Persson, Mia ; Sledneu, Dzmitry
Date 2017
English abstract
We study the complexity of the so called semi-disjoint bilinear forms over different semi-rings, in particular the n-dimensional vector convolution and n x n matrix product. We consider a powerful unit-cost 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 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.
Conference
International Conference on Theory and Applications of Models of Computation (20-22 April, 2017 : Bern, Switzerland)
DOI https://doi.org/10.1007/978-3-319-55911-7_30 (link to publisher's fulltext.)
Publisher Springer
Host/Issue Lecture Notes in Computer Science;
Volume 10185
ISSN 0302-9743
ISBN 978-3-319-55911-7
978-3-319-55910-0
Language eng (iso)
Subject Semi-disjoint bilinear form
Semi-ring
Vector convolution
Matrix multiplication
Distance product
Circuit complexity
Unit-cost ram
Time complexity
Technology
Research Subject Categories::TECHNOLOGY
Handle http://hdl.handle.net/2043/27328 Permalink to this page
Facebook

This item appears in the following Collection(s)

Details

Search


Browse

My Account

Statistics