Matrix multiplication reductions

DOI10.4230/LIPICS.APPROX/RANDOM.2024.34MaRDI QIDQ6920807zbMATH OpenFDO

Authors Ashish Gola, Igor Shinkar, Harsimran Singh

Publication date 6 October 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX/RANDOM.2024.34

zbMATH Keywords

matrix multiplicationreductionsworst case to average case reductions

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites work

• scientific article; zbMATH DE number 5081744 (Why is no real title available?)
• scientific article; zbMATH DE number 7788370 (Why is no real title available?)
• A polynomial bound in Freiman's theorem.
• Average Case Complete Problems
• Efficiently correcting matrix products
• Faster matrix multiplication via asymmetric hashing
• Gaussian elimination is not optimal
• Hardness self-amplification: simplified, optimized, and unified
• Matrix multiplication via arithmetic progressions
• Multiplying matrices faster than coppersmith-winograd
• On the theory of average case complexity
• Partial and Total Matrix Multiplication
• Powers of tensors and fast matrix multiplication
• Quantum worst-case to average-case reductions for all linear problems
• Some Properties of Disjoint Sums of Tensors Related to Matrix Multiplication
• Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, M
• \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication

This page was built for publication: Matrix multiplication reductions

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