BEGIN:VCALENDAR
PRODID:-//Mercury//HGEvent//EN
VERSION:2.0
METHOD:PUBLISH
BEGIN:VEVENT
STATUS:CONFIRMED
LAST-MODIFIED:20120218T171821
PRIORITY:0
CLASS:PUBLIC
UID:ATEvent-eed436ece7e23bbcfe0d4623c4969225
SUMMARY:ARC Colloquium: Virginia Williams\, University of California\, Berkeley
DESCRIPTION:Abstract:\nIn 1987 Coppersmith and Winograd presented an algorithm to multiply two n by n matrices using O(n^{2.3755}) arithmetic operations.\nThis algorithm has remained the theoretically fastest approach for matrix multiplication for 24 years. We have recently been able to design an algorithm that multiplies n by n matrices and uses at most O(n^{2.3727}) arithmetic operations\, thus improving the Coppersmith-Winograd running time.\nThe improvement is based on a recursive application of the original Coppersmith-Winograd construction\, together with a general theorem that reduces the analysis of the algorithm running time to solving a nonlinear constraint program.\nThe final analysis is then done by numerically solving this program.\nTo fully optimize the running time we utilize an idea from independent work by Stothers who claimed an O(n^{2.3737}) runtime in his Ph.D. thesis.\nThe aim of the talk will be to give some intuition and to highlight the main new ideas needed to obtain the improvement.\n
DTSTART:20120130T130000
DTEND:20120130T130000
CREATED:20120218T171821
DTSTAMP:20120218T171821
SEQUENCE:0
LOCATION:
END:VEVENT
END:VCALENDAR