[Proof Complexity] MIAO seminar Thu Dec 1 at 14:00 CET with Srikanth Srinivasan: Lower bounds for algebraic formulas

[Jakob Nordström]

Dear all,

On Thursday December 1 at 14:00 we have the pleasure of welcoming Srikanth Srinivasan from Aarhus University, who will give a talk titled "Lower bounds for algebraic formulas". 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 warmly welcome on UCPH campus --- the exact location will be communicated later. Other participants are equally warmly 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://youtube.com/@MIAOresearch 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 a self-contained 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, in what is an unusally intense period of seminars we have upcoming presentations on Wednesday November 23 on MaxSAT solving by Tobias Paxian, on Friday November 25 on sums-of-squares by Shuo Pang, and on Monday November 28 on certifying combinatorial solvers by a trio of speakers including yours truly. 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


**********

Thursday Dec 1 at 14:00 in Copenhagen and on Zoom
Lower bounds for algebraic formulas
(Srikanth Srinivasan, Aarhus University)

Say we have a multivariate polynomial P(x_1,..., x_n). An algebraic formula for P is just an algebraic expression for P with nested additions and multiplications. A small formula for P implies an efficient algorithm for evaluating P, and so a lower bound on the size of any such expression implies that P is possibly hard to evaluate.

How would you show that your favourite polynomial P has no small formula? In this talk, we will see a technique (building on works of Nisan, Wigderson and Raz) for doing this that combines some linear algebra with random restrictions, which are a classical tool in circuit complexity. This helps us prove lower bounds for special kinds of algebraic formulas, called set-multilinear formulas.

Based on joint work with Nutan Limaye (ITU) and Sébastien Tavenas (USMB, Univ Grenoble). The paper can be found at https://eccc.weizmann.ac.il/report/2021/094/ .


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