[Proof Complexity] Seminar Tue Oct 4 at 14:00 CET with Robert Andrews: Matrix multiplication and polynomial identity testing

[Jakob Nordström]

Dear all,

On Tuesday October 4 at 14:00 CET it is our pleasure to invite you to a seminar with Robert Andrews from the University of Illinois Urbana-Champaign titled "Matrix multiplication and polynomial identity testing". You find the abstract at the bottom of this message.

We will run this as a hybrid seminar at the University of Copenhagen. Local participants are welcome on UCPH campus --- the exact location will be communicated later. Other participants are still welcome to join virtually at https://lu-se.zoom.us/j/61925271827. Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://www.youtube.com/channel/UCN0G2Wfl9-sAKrVLVza7z4A for people who would like to hear the talk but cannot attend.

Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break a ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners an overview of some exciting research results, and after the break people who have the time and interest will get an opportunity to really get into the technical details. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No questions asked; no excuses needed.)

More information about upcoming MIAO seminars can be found at http://www.jakobnordstrom.se/miao-seminars/. In particular, don't miss the seminars with Albert Atserias on Friday this week and Susanna de Rezende on Wednesday next week! If you do not wish to receive these announcements, or receive several copies of them, please send a message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********

Tuesday Oct 4 at 14:00 at University of Copenhagen and on Zoom
Matrix multiplication and polynomial identity testing
(Robert Andrews, University of Illinois Urbana-Champaign)

Determining the complexity of matrix multiplication is a fundamental problem of theoretical computer science. It is popularly conjectured that ω, the matrix multiplication exponent, equals 2. If true, this conjecture would yield fast algorithms for a wide array of problems in linear algebra and beyond. But what if ω > 2? In this talk, I will describe how lower bounds on ω can be used to make progress on derandomizing polynomial identity testing.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +46 70 742 21 98
http://www.jakobnordstrom.se