Speaker: Sriknath Srinivasan (Department of Mathematics, IIT Bombay and
Department of Computer Science, Aarhus University)
Title: A Recent Result in Algebraic Complexity Theory
Time, Day and Date: 16:00, Wednesday, August 4.
Abstract: Given a multivariate polynomial P from C[x_1,...,x_n], one
can always write it as a sum of monomials, i.e. a sum of products of
variables. However, for most polynomials, such an expression is very
verbose, and one can ask if more complicated but succinct expressions
can be found. Such expressions can take the form of a sum of products
of sums of variables, or a sum of products of sums of products, and so
on.
The main result here is negative, showing that for some interesting
families of polynomials (e.g. the Determinant), there are no such
"small" expressions.
The aim of the talk is to present the formal statement of the above
result and the motivation behind it, which stems from an algebraic
analogue of the P vs. NP question (due to Valiant). If there is time,
I might even present (part of) the proof, which is short and
elementary, needing only some combinatorial and linear-algebraic
arguments.
Joint work with Nutan Limaye (IITB CSE) and Sébastien Tavenas (Univ.
Grenoble Alpes, Univ. Savoie Mont Blanc).
Join Zoom Meeting
https://zoom.us/j/96441833399?pwd=OWlIcnFabHIzL1Y3ajhlbzhZalhYdz09
Meeting ID: 964 4183 3399
Passcode: 313170