Lower Bounds for Matrix Product

Title: Lower Bounds for Matrix Product

Research Question: Can matrix product be computed by a circuit of size O(n2)?

Methodology: The researchers used the model of arithmetic circuits, which is the most general model for computing polynomial functions. They considered two other models: quadratic circuits and bilinear circuits. In these models, product gates are applied only on two linear functions.

Results: The researchers proved lower bounds on the number of product gates in bilinear and quadratic circuits that compute the product of two n×nmatrices over finite fields. They improved the former results by showing that the number of product gates in any bilinear (or quadratic) circuit is at least 3 n2−o(n2) and (2 .5 +1.5 p3−1)n2−o(n2) respectively.

Implications: These results improve the understanding of the complexity of matrix product computation. They also provide a lower bound on the size of circuits that can be used to compute matrix product, which is useful for comparing the efficiency of different computational methods.

Link to Article: https://arxiv.org/abs/0201001v1 Authors: arXiv ID: 0201001v1