Date & Time:
February 21, 2023 3:30 pm – 4:30 pm
Location:
Kent 102, 1020 E 58th St, Chicago, IL, 60637
02/21/2023 03:30 PM 02/21/2023 04:30 PM America/Chicago Srikanth Srinivasan (Aarhus) – Lower Bounds for Set-Multilinear Algebraic Formulas Kent 102, 1020 E 58th St, Chicago, IL, 60637

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

Speakers

Srikanth Srinivasan

Associate Professor of Computer Science, Aarhus University

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.

Related News & Events

Students posing at competition
No Name

UChicago Undergrad Team Places Second Overall In Regionals For World’s Largest Programming Competition

Mar 17, 2023
Haifeng Xu
No Name

New CS and DSI Faculty Haifeng Xu Brings Strategic Intelligence to NeurIPS 2022

Nov 28, 2022
No Name

UChicago CS Research Finds New Angle on Database Query Processing with Geometry

Nov 08, 2022
No Name

Asst. Prof. Aloni Cohen Receives Award For Revealing Flaws in Deidentifying Data

Sep 09, 2022
No Name

UChicago Hosts NSF Workshop on Frontiers of Quantum Advantage

Aug 15, 2022
No Name

New 2022-23 Faculty Add Expertise in Linguistics, Visualization, Economics, and Data Science Education

Aug 11, 2022
No Name

UChicago Co-Leads $10 Million NSF Institute on Foundations of Data Science

Aug 09, 2022
No Name

Bill Fefferman Comments on New Standards for Quantum-Proof Cryptography

Jul 07, 2022
No Name

UChicago London Colloquium Features Data Science, Quantum Research

Jul 01, 2022
No Name

Faculty Bill Fefferman and Chenhao Tan Receive Google Research Scholar Awards

Jun 21, 2022
No Name

First-Year PhD Student Co-Authors Outstanding Paper Award Winner at TQC 2022

Apr 28, 2022
No Name

Quanta Magazine Features Prof. Bill Fefferman’s Work on Quantum Algorithms

Jan 20, 2022
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube