<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div class="x-apple-outlook-blockquote" style="-webkit-text-size-adjust: auto;"><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 12pt; font-family: Helvetica;">Srikanth Srinivasan</span></b><o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt; font-family: Helvetica;">Aarhus University, Aarhus, Denmark</span></b><o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><img width="217" height="290" id="Picture_x0020_3" src="cid:2BB9D599-5174-4201-804F-EF7EB91FDDC1" alt="image001.jpg" _mf_state="1" title="null" style="width: 2.2604in; height: 3.0208in;"><o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt; font-family: Helvetica;"> </span></b><o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt; font-family: Helvetica;"> </span></b><o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt;"><span dir="ltr" style="text-decoration: underline;">Tuesday, </span></span></b><b><span style="font-size: 11pt;"><span dir="ltr" style="text-decoration: underline;">February 21</span><span dir="ltr" style="text-decoration: underline;">, 202</span><span dir="ltr" style="text-decoration: underline;">3</span><span dir="ltr" style="text-decoration: underline;"> at 3:30pm</span></span></b><o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt; background-color: yellow;">Kent Chemical Laboratory, Room 102</span></b><o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p></div><p style="-webkit-text-size-adjust: auto; margin: 0in;"><b><i><span style="font-size: 12pt;">Title:</span></i></b><span style="font-size: 12pt;"> <span style="color: rgb(33, 33, 33);">Lower Bounds for Set-Multilinear Algebraic Formulas</span></span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p style="-webkit-text-size-adjust: auto; margin: 0in;"><b><i><span style="font-size: 12pt;">Abstract:</span></i></b><b><span style="font-size: 12pt;"> </span></b><span style="font-size: 12pt;"> <span style="color: rgb(33, 33, 33);">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.<br><span class="apple-converted-space"> </span><br>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.<br><br><br><br><br></span></span><o:p></o:p></p><p style="-webkit-text-size-adjust: auto; margin: 0in;"><span style="font-size: 12pt; color: rgb(33, 33, 33);">Based on joint work with Nutan Limaye (ITU) and Sébastien Tavenas (USMB, Univ Grenoble). The paper can be found at: </span><a href="https://urldefense.com/v3/__https:/eccc.weizmann.ac.il/report/2021/094/__;!!BpyFHLRN4TMTrA!_jvh72boR_G5MShz_-df-YHKy6ZC_4Ix4MKW3SmM2EftKbfGSUk7mmQp204YbXhtxk6Ye22MkRXZ98i-wqIT_HxuEw$" style="color: blue;"><span style="font-size: 12pt;">https://eccc.weizmann.ac.il/report/2021/094/</span></a><span class="apple-converted-space"><span style="font-size: 12pt; color: rgb(33, 33, 33);"> </span></span></p><div dir="ltr"></div></body></html>