BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Joshua Grochow (University of Colorado at Boulder) DTSTART:20201124T181500Z DTEND:20201124T184500Z DTSTAMP:20260423T023013Z UID:LA-CoCo/8 DESCRIPTION:Title: Designing Strassen's algorithm for matrix multiplication\nby Joshua Gr ochow (University of Colorado at Boulder) as part of LA Combinatorics and Complexity Seminar\n\n\nAbstract\nIn 1969\, Strassen shocked the world by showing that two n x n matrices could be multiplied in time asymptotically less than $O(n^3)$. While the recursive construction in his algorithm is very clear\, the key gain was made by showing that $2 \\times 2$ matrix mu ltiplication could be performed with only $7$ multiplications instead of $ 8$. The latter construction was arrived at by a process of elimination and appears to come out of thin air. We give a transparent proof of this algo rithm using only a simple unitary $2$-design (coming from an irreducible r epresentation of a finite group) and a few easy lines of calculation. More over\, using basic facts from the representation theory of finite groups\, we use $2$-designs coming from group orbits to generalize our constructio n to all $n$ (although the resulting algorithms aren't optimal for $n \\ge 3$). \n\nThe talk will include background on matrix multiplication\, and we'll be able to give the full proof. Based on joint work with C. Moore.\n LOCATION:https://researchseminars.org/talk/LA-CoCo/8/ END:VEVENT END:VCALENDAR