On the Complexity of Matrix Product

DOI10.1137/S0097539702402147MaRDI QIDQ4429689zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Ran Raz

Publication date 28 September 2003

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

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

zbMATH Keywords

lower boundssingular valuesarithmetic circuitscircuit complexityalgebraic complexitybounded coefficients model

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Lower bounds for matrix product, in bounded depth circuits with arbitrary gates
• Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
• Linear Circuits over $\operatorname{GF}(2)$
• Lower Bounds for Matrix Product
• A direct version of Shamir and Snir's lower bounds on monotone circuit depth

Cited in

(29)

• REVISITING MATRIX PRODUCT ON MASTER-WORKER PLATFORMS
• A super-quadratic lower bound for depth four arithmetic circuits
• Identifying complexity by means of matrices
• Approximate computation of scalar products
• Efficient Bayesian inference of general Gaussian models on large phylogenetic trees
• Binary determinantal complexity
• A note on the use of determinant for proving lower bounds on the size of linear circuits
• Lower Bounds for Matrix Product
• Lower bounds for matrix product, in bounded depth circuits with arbitrary gates
• Fast linear algebra is stable
• A refined laser method and faster matrix multiplication
• Fast matrix multiplication is stable
• Arithmetic circuit lower bounds via MaxRank
• Lower bounds for the matrix chain ordering problem (extended abstract)
• A nonlinear lower bound for constant depth arithmetical circuits via the discrete uncertainty principle
• Average-case complexity of the min-sum matrix product problem
• Removing the log factor from (,+)-products on bounded range integer matrices
• Prototype based granular neuro-fuzzy system for regression task
• A direct version of Shamir and Snir's lower bounds on monotone circuit depth
• Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
• Some algorithms related to matrices with entries in a finite field
• Length Complexity of Tensor Products
• Area-time tradeoff for rectangular matrix multiplication in VLSI models
• Linear Circuits over $\operatorname{GF}(2)$
• On matrix multiplication and polynomial identity testing
• Algorithm design for tensor units
• Matrix rigidity of random Toeplitz matrices
• Lower bounds on the bounded coefficient complexity of bilinear maps
• Fractal-like matrices

This page was built for publication: On the Complexity of Matrix Product

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