BARC/MIAO talk by Srikanth Srinivasan

▤ Summary

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. Based on joint work with Nutan Limaye (ITU) and Sébastien Tavenas (USMB, Univ Grenoble). 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.

▦ Linked Companies