TY - GEN

T1 - Complexity of linear operators

AU - Kulikov, Alexander S.

AU - Mikhailin, Ivan

AU - Mokhov, Andrey

AU - Podolskii, Vladimir

N1 - Funding Information: Funding Alexander S. Kulikov: The results presented in Section 3 are supported by Russian Science Foundation (18-71-10042). Vladimir Podolskii: The results presented in Section 4 are supported by Russian Science Foundation (16-11-10252). Publisher Copyright: © Alexander S. Kulikov, Ivan Mikhailin, Andrey Mokhov, and Vladimir Podolskii; licensed under Creative Commons License CC-BY

PY - 2019/12

Y1 - 2019/12

N2 - Let A ∈ {0, 1}n×n be a matrix with z zeroes and u ones and x be an n-dimensional vector of formal variables over a semigroup (S, ◦). How many semigroup operations are required to compute the linear operator Ax? As we observe in this paper, this problem contains as a special case the well-known range queries problem and has a rich variety of applications in such areas as graph algorithms, functional programming, circuit complexity, and others. It is easy to compute Ax using O(u) semigroup operations. The main question studied in this paper is: can Ax be computed using O(z) semigroup operations? We prove that in general this is not possible: there exists a matrix A ∈ {0, 1}n×n with exactly two zeroes in every row (hence z = 2n) whose complexity is Θ(nα(n)) where α(n) is the inverse Ackermann function. However, for the case when the semigroup is commutative, we give a constructive proof of an O(z) upper bound. This implies that in commutative settings, complements of sparse matrices can be processed as efficiently as sparse matrices (though the corresponding algorithms are more involved). Note that this covers the cases of Boolean and tropical semirings that have numerous applications, e.g., in graph theory. As a simple application of the presented linear-size construction, we show how to multiply two n × n matrices over an arbitrary semiring in O(n2) time if one of these matrices is a 0/1-matrix with O(n) zeroes (i.e., a complement of a sparse matrix).

AB - Let A ∈ {0, 1}n×n be a matrix with z zeroes and u ones and x be an n-dimensional vector of formal variables over a semigroup (S, ◦). How many semigroup operations are required to compute the linear operator Ax? As we observe in this paper, this problem contains as a special case the well-known range queries problem and has a rich variety of applications in such areas as graph algorithms, functional programming, circuit complexity, and others. It is easy to compute Ax using O(u) semigroup operations. The main question studied in this paper is: can Ax be computed using O(z) semigroup operations? We prove that in general this is not possible: there exists a matrix A ∈ {0, 1}n×n with exactly two zeroes in every row (hence z = 2n) whose complexity is Θ(nα(n)) where α(n) is the inverse Ackermann function. However, for the case when the semigroup is commutative, we give a constructive proof of an O(z) upper bound. This implies that in commutative settings, complements of sparse matrices can be processed as efficiently as sparse matrices (though the corresponding algorithms are more involved). Note that this covers the cases of Boolean and tropical semirings that have numerous applications, e.g., in graph theory. As a simple application of the presented linear-size construction, we show how to multiply two n × n matrices over an arbitrary semiring in O(n2) time if one of these matrices is a 0/1-matrix with O(n) zeroes (i.e., a complement of a sparse matrix).

KW - Algorithms

KW - Circuit complexity

KW - Commutativity

KW - Linear operators

KW - Lower bounds

KW - Range queries

KW - Upper bounds

UR - http://www.scopus.com/inward/record.url?scp=85076351813&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ISAAC.2019.17

DO - 10.4230/LIPIcs.ISAAC.2019.17

M3 - Conference contribution

AN - SCOPUS:85076351813

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 30th International Symposium on Algorithms and Computation, ISAAC 2019

A2 - Lu, Pinyan

A2 - Zhang, Guochuan

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 30th International Symposium on Algorithms and Computation, ISAAC 2019

Y2 - 8 December 2019 through 11 December 2019

ER -