{"96961":{"#nid":"96961","#data":{"type":"event","title":"ARC Colloquium: Virginia Williams, University of California, Berkeley","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EIn 1987 Coppersmith and Winograd presented an algorithm to multiply two n by n matrices using O(n^{2.3755}) arithmetic operations.\u003C\/p\u003E\u003Cp\u003EThis 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.\u003C\/p\u003E\u003Cp\u003EThe 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.\u003C\/p\u003E\u003Cp\u003EThe final analysis is then done by numerically solving this program.\u003C\/p\u003E\u003Cp\u003ETo 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.\u003C\/p\u003E\u003Cp\u003EThe aim of the talk will be to give some intuition and to highlight the main new ideas needed to obtain the improvement.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Multiplying matrices faster than Coppersmith-Winograd"}],"uid":"27263","created_gmt":"2012-01-26 14:17:20","changed_gmt":"2016-10-08 01:57:44","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-01-30T12:00:00-05:00","event_time_end":"2012-01-30T12:00:00-05:00","event_time_end_last":"2012-01-30T12:00:00-05:00","gmt_time_start":"2012-01-30 17:00:00","gmt_time_end":"2012-01-30 17:00:00","gmt_time_end_last":"2012-01-30 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Ca href=\u0022mailto:ndongi@cc.gatech.edu\u0022\u003Endongi@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}