BARC/MIAO talk by Nutan Limaye
Friday, 12 November 2021, Nutan Limaye, Associate Professor at ITU in Copenhagen, will give a talk on "Superpolynomial lower bounds for low-depth circuits".
This talk will be offered as a hybrid at the University of Copenhagen and on Zoom. Physical attendees are welcome on campus (HCØ, aud. 10), while virtual attendees can refer to http://www.jakobnordstrom.se/videoseminars/ for information on how to join on Zoom.
Title:
Superpolynomial lower bounds for low-depth circuits
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.
In the first part of this two-part talk, Nutan will present the statements of the main results and some background. In the second part of the talk, she will give some proof details.
This is a joint work with Srikanth Srinivasan and Sébastien Tavenas.
Bio:
Nutan Limaye is an Associate Professor at ITU Copenhagen. She finished her PhD in 2009 and after a short post-doc stint at Tata Institute of Fundamental Research (TIFR) she joined as a faculty member at IIT Bombay. She was an assistant professor at IIT Bombay from 2010 to 2016 and associate professor from 2016 to 2021.
Her research interests lie in Complexity Theory. Specifically, she is interested in Boolean and algebraic circuit lower bounds.