[Colloquium] U of C - CS Theory Seminar - Srikanth Srinivasan, February 21, 2023

[Jose J Fragoso]

UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS



Srikanth Srinivasan
Aarhus University, Aarhus, Denmark


[srikanth Srinivasan]


Tuesday, February 21, 2023 at 3:30pm
Kent Chemical Laboratory, Room 102



Title: Lower Bounds for Set-Multilinear Algebraic Formulas


Abstract:  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/<https://urldefense.com/v3/__https:/eccc.weizmann.ac.il/report/2021/094/__;!!BpyFHLRN4TMTrA!_jvh72boR_G5MShz_-df-YHKy6ZC_4Ix4MKW3SmM2EftKbfGSUk7mmQp204YbXhtxk6Ye22MkRXZ98i-wqIT_HxuEw$>



Bio:  I’m an Associate Professor of Computer Science at Aarhus University in Aarhus, Denmark.  I received my PhD from The Institute of Mathematical Sciences, in Tamil Nadu,  India.



Host: Alexander Razborov













-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20230221/995b1e97/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 24293 bytes
Desc: image001.jpg
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20230221/995b1e97/attachment-0001.jpg>