On commutativity and approximation

DOI10.1016/0304-3975(83)90068-3zbMath0548.68036OpenAlexW2021882883MaRDI QIDQ799369

Dario Andrea Bini

Publication date: 1984

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(83)90068-3

zbMATH Keywords

algebraic complexitypolynomial evaluationmatrix-vector producttensor rankmatrix multiplicationapproximate algorithmapproximate complexitycommutative border rank

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Related Items

The bit complexity of matrix multiplication and of related computations in linear algebra. The segmented \(\lambda\) algorithms, Matrix structures in parallel matrix computations, Lower bound for the approximative complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics
• Some elementary proofs of lower bounds in complexity theory
• \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
• Approximate Solutions for the Bilinear Form Computational Problem
• On the Complexity of Bilinear Forms with Commutativity
• Partial and Total Matrix Multiplication
• On the Asymptotic Complexity of Matrix Multiplication
• Polynomials with Rational Coefficients Which are Hard to Compute
• On the number of multiplications necessary to compute certain functions