[Proof Complexity] Seminar Fri Nov 12 at 14:00 CET with Nutan Limaye: Superpolynomial lower bounds against low-depth algebraic circuits

[Jakob Nordström]

Dear all,

It is an immense pleasure to invite you to a joint BARC/MIAO seminar on Friday November 12 at 14:00 CET with Nutan Limaye, who recently joined the IT University of Copenhagen. Nutan will be talking about her exciting paper "Superpolynomial lower bounds against low-depth algebraic circuits", which has received the best paper award at FOCS 2021. Please see the bottom of this message for the abstract.

In addition to the excitement caused by this breakthrough on a decades old problem, we are also excited to run this as a hybrid seminar at the University of Copenhagen. Local participants are welcome on 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 video seminars can be found at http://www.jakobnordstrom.se/videoseminars/ . In particular, this coming Friday October 22 at 14:00 Magnus Myreen from Chalmers University of Technology is speaking about "Verified proof checkers"; on Monday October 25 at 14:00 there will be a seminar with Robert Robere from McGill University titled "Proof complexity lower bounds by composition"; and on Monday Nov 8 at 14:00 Sajin Koroth at Simon Fraser University is giving a seminar "Lifting with inner-product and other low discrepancy gadgets". 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

**********

Joint BARC/MIAO seminar Friday Nov 12 at 14:00 CET
Superpolynomial lower bounds against low-depth algebraic circuits
(Nutan Limaye, IT University of Copenhagen)

Every multivariate polynomial P(X) can be written as a sum of monomials, i.e. a sum of products of variables and field constants. In general, the size of such an expression is the number of monomials that have a non-zero coefficient in P.

What happens if we add another layer of complexity, and consider sums of products of sums (of variables and field constants) expressions? Now, it becomes unclear how to prove that a given polynomial P(X) does not have small expressions. In this result, we solve exactly this problem.

More precisely, we prove that certain explicit polynomials have no polynomial-sized "Sigma-Pi-Sigma" (sums of products of sums) representations. We can also show similar results for Sigma-Pi-Sigma-Pi, Sigma-Pi-Sigma-Pi-Sigma and so on for all "constant-depth" expressions.

In the first part of this two-part talk, I will present the statements of the main results and some background. In the second part of the talk, I will give some proof details.

This is a joint work with Srikanth Srinivasan and Sébastien Tavenas.


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