Description

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

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

Date

Wed, August 4, 2021

Start Time

4:00pm IST

Priority

5-Medium

Access

Public

Created by

DEFAULT ADMINISTRATOR

Updated

Mon, August 2, 2021 2:34pm IST