[Proof Complexity] Seminar Mon Apr 26 at 14:00 CET with Ben Lee Volk: Recent lower bounds in algebraic complexity theory

[Jakob Nordström]

Dear all,

On Monday Apr 26 at 14:00 CET we will have a seminar with Ben Lee Volk from the University of Texas at Austin titled "Recent lower bounds in algebraic complexity theory". See below for the abstract.

We will meet 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 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 video seminars can be found at http://www.csc.kth.se/~jakobn/videoseminars/ (an address that should change soonish, but for now it is what it is). If you do not wish to receive these announcements, or receive several copies of them, please send a message to jakob.nordstrom at cs.lth.se.

Best regards,
Jakob Nordström

**********

Monday Apr 26 at 14:00
Recent lower bounds in algebraic complexity theory
(Ben Lee Volk, University of Texas at Austin)

Algebraic complexity theory studies the complexity of solving algebraic computational tasks using algebraic models of computation. One major problem in this area is to prove lower bounds on the number of arithmetic operations required for computing explicit polynomials. This natural mathematical problem is the algebraic analog of the famous P vs. NP problem. It also has tight connections to other classical mathematical areas and to fundamental questions in complexity theory.

In this talk I will provide background and then present some recent progress on proving lower bounds for models of algebraic computation, such as the algebraic analogs of NC^1 and NL.

Based on joint works with Prerona Chatterjee, Mrinal Kumar and Adrian She.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +46 70 742 21 98
http://www.csc.kth.se/~jakobn/ (webpages still in transit)