Skip to content
JournalsWorldThe Global Research Discovery Platform
Login Sign Up
SCHOLARLY PUBLICATION

Multiplying matrices faster than coppersmith-winograd

Virginia Vassilevska Williams

📖 ACM Symposium on Theory of Computing (STOC) 📅 2012-05-19 🔗 DOI: 10.1145/2213977.2214056
View Official Paper ↗

📄 Abstract

We develop an automated approach for designing matrix multiplication algorithms based on constructions similar to the Coppersmith-Winograd construction. Using this approach we obtain a new improved bound on the matrix multiplication exponent ω<2.3727.

📤 Share this page

Found this useful? Share it with your network.

𝕏XfFacebookinLinkedIn✆WhatsApp✈Telegram✉EmailMMendeley
✓ Link copied! Paste it on ResearchGate / Academia.edu

🔬 Related Research Papers

ACM Symposium on Theory of Computing (ST

Separating succinct non-interactive arguments from all falsifiable assumptions

Craig Gentry, Daniel Wichs 2011-06-06 · Read paper → ACM Symposium on Theory of Computing (ST

Reusable garbled circuits and succinct functional encryption

Shafi Goldwasser, Yael Tauman Kalai et al. 2013-05-28 · Read paper → ACM Symposium on Theory of Computing (ST

The complexity of computing a Nash equilibrium

Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou 2006-05-21 · Read paper → ACM Symposium on Theory of Computing (ST

The PCP theorem by gap amplification

Irit Dinur 2006-05-21 · Read paper → ACM Symposium on Theory of Computing (ST

Differential privacy under continual observation

Cynthia Dwork, Moni Naor et al. 2010-06-05 · Read paper → ACM Symposium on Theory of Computing (ST

How to use indistinguishability obfuscation

Amit Sahai, Brent R. Waters 2014-05-31 · Read paper → ACM Symposium on Theory of Computing (ST

Public-key cryptosystems from the worst-case shortest vector problem

Chris Peikert 2009-05-31 · Read paper → ACM Symposium on Theory of Computing (ST

The computational complexity of linear optics

Scott Aaronson, Alex Arkhipov 2011-06-06 · Read paper → ACM Symposium on Theory of Computing (ST

Low-rank matrix completion using alternating minimization

Prateek Jain, Praneeth Netrapalli, Sujay Sanghavi 2013-05-28 · Read paper → ACM Symposium on Theory of Computing (ST

On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption

Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan 2012-05-19 · Read paper → Environmental Toxicology and Chemistry

Analysis of engineered nanomaterials in complex matrices (environment and biota): General considerations and conceptual case studies

Frank von der Kammer, P. Lee Ferguson et al. 2011-10-21 · Read paper → SIAM Journal on Optimization

Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations

Min Tao, Xiaoming Yuan 2011-01-01 · Read paper →