Srikanth Srinivasan (Aarhus) - Lower Bounds for Set-Multilinear 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 favorite 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/

Host: Alexander Razborov