BARC/MIAO talk by Srikanth Srinivasan

Abstract:

Lower bounds for algebraic formulas
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/.

We are hoping to record the seminar and post on the MIAO Research YouTube channel for people who would like to hear the talk but cannot attend.