On matrix multiplication and polynomial identity testing

DOI10.1137/22M1536169MaRDI QIDQ6911558zbMATH OpenFDO

Authors Robert Andrews

Publication date 24 October 2025

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/22M1536169

zbMATH Keywords

border rankmatrix multiplicationpolynomial identity testing

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Cites work

• \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
• A \(2\mathbf{n}^2-\log_2(\mathbf{n})-1\) lower bound for the border rank of matrix multiplication
• A Deterministic Linear Program Solver in Current Matrix Multiplication Time
• A faster algorithm for solving general LPs
• Arithmetic circuits: a survey of recent results and open questions
• Barriers for fast matrix multiplication from irreversibility
• Closure results for polynomial factorization
• Derandomization from Algebraic Hardness
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Determinantal rings
• Exact arborescences, matchings and cycles
• Fast algorithms for the characteristic polynomial
• Fast matrix multiplication using coherent configurations
• Fast matrix multiplication: limitations of the Coppersmith-Winograd method (extended abstract)
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Further limitations of the known approaches for matrix multiplication
• Gaussian elimination is not optimal
• General context-free recognition in less than cubic time
• Hardness-randomness tradeoffs for bounded depth arithmetic circuits
• scientific article; zbMATH DE number 3910446 (Why is no real title available?)
• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 7561765 (Why is no real title available?)
• scientific article; zbMATH DE number 7150624 (Why is no real title available?)
• scientific article; zbMATH DE number 7788370 (Why is no real title available?)
• Ideals, determinants, and straightening: proving and using lower bounds for polynomial ideals
• Improved bound for complexity of matrix multiplication
• Limits on all known (and some unknown) approaches to matrix multiplication
• Limits on the universal method for matrix multiplication
• Lower Bounds for Matrix Product
• Matrix multiplication via arithmetic progressions
• Multiplying matrices faster than coppersmith-winograd
• New Fast Algorithms for Matrix Operations
• On cap sets and the group-theoretic approach to matrix multiplication
• On the Asymptotic Complexity of Matrix Multiplication
• On the Complexity of Matrix Product
• Partial and Total Matrix Multiplication
• Powers of tensors and fast matrix multiplication
• Progress on polynomial identity testing
• Progress on polynomial identity testing. II
• Randomness efficient identity testing of multivariate polynomials
• Relations between exact and approximate bilinear algorithms. Applications
• Relative bilinear complexity and matrix multiplication.
• Solving Linear Programs in the Current Matrix Multiplication Time
• Some Properties of Disjoint Sums of Tensors Related to Matrix Multiplication
• The complexity of factors of multivariate polynomials
• The complexity of partial derivatives
• Triangular Factorization and Inversion by Fast Matrix Multiplication
• Unitäre Transformationen großer Matrizen

This page was built for publication: On matrix multiplication and polynomial identity testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6911558)