Name
Abstract | ||
|---|---|---|
We study the average-case complexity of min-sum product of matrices, which is a fundamental operation that has many applications in computer science. We focus on optimizing the number of “algebraic” operations (i.e., operations involving real numbers) used in the computation, since such operations are usually expensive in various environments. We present an algorithm that can compute the min-sum product of two n×n real matrices using only O(n2) algebraic operations, given that the matrix elements are drawn independently and identically from some fixed probability distribution satisfying several constraints. This improves the previously best known upper-bound of O(n2logn). The class of probability distributions under which our algorithm works include many important and commonly used distributions, such as uniform distributions, exponential distributions, folded normal distributions, etc. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.tcs.2015.09.008 | Theoretical Computer Science |
Keywords | Field | DocType |
Min-sum product,Min-plus product,Matrix multiplication | Average-case complexity,Discrete mathematics,Combinatorics,Normal distribution,2 × 2 real matrices,Matrix (mathematics),Probability distribution,Freivalds' algorithm,Matrix multiplication,Mathematics,Algebraic operation | Journal |
Volume | Issue | ISSN |
609 | P1 | 0304-3975 |
Citations | PageRank | References |
0 | 0.34 | 13 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ken C. K. Fong | 1 | 2 | 1.75 |
| Minming Li | 2 | 821 | 82.16 |
| Hongyu Liang | 3 | 84 | 16.39 |
| Linji Yang | 4 | 58 | 5.17 |
| Hao Yuan | 5 | 3 | 3.76 |