On the Complexity of Matrix Product

DOI10.1137/S0097539702402147zbMath1026.68060OpenAlexW1968408352WikidataQ56115907 ScholiaQ56115907MaRDI QIDQ4429689

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

singular valueslower boundscircuit complexityalgebraic complexityarithmetic circuitsbounded coefficients model

Mathematics Subject Classification ID

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

Related Items (10)

Binary determinantal complexity ⋮ A nonlinear lower bound for constant depth arithmetical circuits via the discrete uncertainty principle ⋮ Matrix rigidity of random Toeplitz matrices ⋮ Fast matrix multiplication is stable ⋮ Prototype based granular neuro-fuzzy system for regression task ⋮ Fast linear algebra is stable ⋮ Some algorithms related to matrices with entries in a finite field ⋮ Efficient Bayesian inference of general Gaussian models on large phylogenetic trees ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Fractal-like matrices

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