{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:21:21Z","timestamp":1750306881675,"version":"3.41.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2012,12,19]],"date-time":"2012-12-19T00:00:00Z","timestamp":1355875200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2012,12,19]]},"abstract":"<jats:p>\n            The exponent \u03c9 of matrix multiplication is the infimum over all real numbers\n            <jats:italic>c<\/jats:italic>\n            such that for all \u03b5 &gt; 0 there is an algorithm that multiplies\n            <jats:italic>n - n<\/jats:italic>\n            matrices using at most O(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>c+\u03b5<\/jats:sup>\n            ) arithmetic operations over an arbitrary field. A trivial lower bound on \u03c9 is 2, and the best known upper bound until recently was \u03c9 &lt; 2.376 achieved by Coppersmith and Winograd in 1987. There were two independent improvements on \u03c9, one by Stothers in 2010 who showed that \u03c9 &lt; 2.374, and one by myself that ultimately resulted in \u03c9 &lt; 2.373. Here I discuss the road to these improvements and conclude with some open questions.\n          <\/jats:p>","DOI":"10.1145\/2421119.2421134","type":"journal-article","created":{"date-parts":[[2013,1,2]],"date-time":"2013-01-02T13:23:15Z","timestamp":1357132995000},"page":"57-59","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Algorithms column"],"prefix":"10.1145","volume":"43","author":[{"given":"Samir","family":"Khuller","sequence":"first","affiliation":[{"name":"University of Maryland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,12,19]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"The design and analysis of computer algorithms","author":"Aho A. V.","year":"1974","unstructured":"A. V. Aho , J. E. Hopcroft , and J. Ullman . The design and analysis of computer algorithms . Addison-Wesley Longman Publishing Co. , Boston, MA , 1974 . A. V. Aho, J. E. Hopcroft, and J. Ullman. The design and analysis of computer algorithms. Addison-Wesley Longman Publishing Co., Boston, MA, 1974."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02575865"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90113-3"},{"key":"e_1_2_1_4_1","first-page":"45","volume-title":"Proc. FOCS","author":"Bl\u00e4ser M.","unstructured":"M. Bl\u00e4ser . A lower bound for the rank of matrix multiplication over arbitrary fields . In Proc. FOCS , pages 45 --, 1999. M. Bl\u00e4ser. A lower bound for the rank of matrix multiplication over arbitrary fields. In Proc. FOCS, pages 45--, 1999."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.77"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"e_1_2_1_7_1","volume-title":"New lower bounds for the rank of matrix multiplication. CoRR, abs\/1206.1530","author":"Landsberg J. M.","year":"2012","unstructured":"J. M. Landsberg . New lower bounds for the rank of matrix multiplication. CoRR, abs\/1206.1530 , 2012 . J. M. Landsberg. New lower bounds for the rank of matrix multiplication. CoRR, abs\/1206.1530, 2012."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780574"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210032"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796471"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702405954"},{"key":"e_1_2_1_12_1","unstructured":"A. Stothers. Ph.D. Thesis U. Edinburgh 2010.  A. Stothers. Ph.D. Thesis U. Edinburgh 2010."},{"issue":"264","key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1515\/crll.1973.264.184","volume":"1973","author":"V. Strassen. Vermeidung von Division","year":"1973","unstructured":"V. Strassen. Vermeidung von Division en . Crelle J. Reine Angew. Math. , 1973 ( 264 ): 184 -- 202 , 1973 . V. Strassen. Vermeidung von Divisionen. Crelle J. Reine Angew. Math., 1973(264):184--202, 1973.","journal-title":"Crelle J. Reine Angew. Math."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80046-8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/567112.567114"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2421119.2421134","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2421119.2421134","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:18:34Z","timestamp":1750234714000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2421119.2421134"}},"subtitle":["An overview of the recent progress on matrix multiplication by Virginia Vassilevska Williams"],"short-title":[],"issued":{"date-parts":[[2012,12,19]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,12,19]]}},"alternative-id":["10.1145\/2421119.2421134"],"URL":"https:\/\/doi.org\/10.1145\/2421119.2421134","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2012,12,19]]},"assertion":[{"value":"2012-12-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}