research-article

Algebraic complexity theory and matrix multiplication

Author:

François Le GallAuthors Info & Claims

ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation

Page 23

https://doi.org/10.1145/2608628.2627493

Published: 23 July 2014 Publication History

Get Access

Abstract

This tutorial will give an overview of algebraic complexity theory focused on bilinear complexity, and describe several powerful techniques to analyze the complexity of computational problems from linear algebra, in particular matrix multiplication. The presentation of these techniques will follow the history of progress on constructing asymptotically fast algorithms for matrix multiplication, and include its most recent developments.

Cited By

View all

Araya ETyagi H(2024)Graph Matching via convex relaxation to the simplexFoundations of Data Science10.3934/fods.2024034(0-0)Online publication date: 2024
https://doi.org/10.3934/fods.2024034
Pervin NSanam TImtiaz H(2024)Privacy-preserving human activity recognition using principal component-based wavelet CNNSignal, Image and Video Processing10.1007/s11760-024-03535-018:12(9141-9155)Online publication date: 2-Sep-2024
https://doi.org/10.1007/s11760-024-03535-0
Grandoni FItaliano GŁukasiewicz AParotsidis NUznański PMarx D(2021)All-pairs LCA in DAGsProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458082(273-289)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458082
Show More Cited By

Index Terms

Algebraic complexity theory and matrix multiplication

Recommendations

Powers of tensors and fast matrix multiplication
ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation

This paper presents a method to analyze the powers of a given trilinear form (a special kind of algebraic construction also called a tensor) and obtain upper bounds on the asymptotic complexity of matrix multiplication. Compared with existing approaches,...
Ubiquity of the exponent of matrix multiplication
ISSAC '20: Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation

The asymptotic exponent of matrix multiplication is the smallest ω such that one may multiply two n × n matrices or invert an n × n matrix in O(n^ω+ε)-complexity for ε > 0 arbitrarily small. One of the biggest open problem in complexity theory and ...
Group-theoretic lower bounds for the complexity of matrix multiplication
TAMC'11: Proceedings of the 8th annual conference on Theory and applications of models of computation

The complexity of multiplication in group algebras is closely related to the complexity of matrix multiplication. Inspired by the recent group-theoretic approach by Cohn and Umans [10] and the algorithms by Cohn et al. [9] for matrix multiplication, we ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation

July 2014

444 pages

ISBN:9781450325011

DOI:10.1145/2608628

Editor:
Katsusuke Nabeshima
The University of Tokushima, Japan
,
General Chairs:
Kosaku Nagasaka
Kobe University, Japan
,
Franz Winkler
RISC, University Linz, Austria
,
Program Chair:
Agnes Szanto
North Carolina State University

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2014

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSAC '14

ISSAC '14: International Symposium on Symbolic and Algebraic Computation

July 23 - 25, 2014

Kobe, Japan

Acceptance Rates

ISSAC '14 Paper Acceptance Rate 51 of 96 submissions, 53%;

Overall Acceptance Rate 395 of 838 submissions, 47%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
178
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)4

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Araya ETyagi H(2024)Graph Matching via convex relaxation to the simplexFoundations of Data Science10.3934/fods.2024034(0-0)Online publication date: 2024
https://doi.org/10.3934/fods.2024034
Pervin NSanam TImtiaz H(2024)Privacy-preserving human activity recognition using principal component-based wavelet CNNSignal, Image and Video Processing10.1007/s11760-024-03535-018:12(9141-9155)Online publication date: 2-Sep-2024
https://doi.org/10.1007/s11760-024-03535-0
Grandoni FItaliano GŁukasiewicz AParotsidis NUznański PMarx D(2021)All-pairs LCA in DAGsProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458082(273-289)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458082
Nakamura SIkematsu YWang YDing JTakagi T(2021)New complexity estimation on the Rainbow-Band-Separation attackTheoretical Computer Science10.1016/j.tcs.2021.09.043896:C(1-18)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.1016/j.tcs.2021.09.043

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Powers of tensors and fast matrix multiplication

Ubiquity of the exponent of matrix multiplication

Group-theoretic lower bounds for the complexity of matrix multiplication