Center for Global Studies

Back to Listing

Nutan Limaye "Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits"

Event Type
Ceremony/Service
Sponsor
Theory Research Group, Department of Computer Science
Location
3401 SC
Virtual
wifi event
Date
Sep 26, 2022   10:00 am  
Speaker
Nutan Limaye, Associate Professor, IT University of Copenhagen
Contact
Candice Steidinger
E-Mail
steidin2@illinois.edu
Phone
217-300-8564
Views
42
Originating Calendar
Computer Science Speakers Calendar

Pre-recorded talk

Abstract: 

Every multivariate polynomial P(X) can be written as a sum of monomials, i.e. a sum of products of variables and field constants. In general, the size of such an expression is the number of monomials that have a non-zero coefficient in P.

What happens if we add another layer of complexity, and consider sums of products of sums (of variables and field constants) expressions? Now, it becomes unclear how to prove that a given polynomial P(X) does not have small expressions. In this result, we solve exactly this problem.

More precisely, we prove that certain explicit polynomials have no polynomial-sized "Sigma-Pi-Sigma" (sums of products of sums) representations. We can also show similar results for Sigma-Pi-Sigma-Pi, Sigma-Pi-Sigma-Pi-Sigma and so on for all "constant-depth" expressions.

The talk is based on a joint work of Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas.

link for robots only