BARC/MIAO talk by Srikanth Srinivasan


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

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.