Talks - Spring 2019

ArithmeticCircuit

Title

Speaker

Date

Time

Venue

Abstract

Lower Bounds for Univariate Polynomials - 1

Pranjal Dutta

1st March 2019

4:00-5:00 PM

KD101

We consider the problem of representing a univariate polynomial f (x) as a sum of low degree polynomials. Our underlying hope is that some such improved proof technique or proof idea might admit a suitable generalization to the multivariate case as well. This could be one potential way to attack the VP versus VNP problem. We also note that there are formal results essentially following from the work of Koiran [Koi11] which imply that seemingly mild lower bounds for a slight variant of the model being considered here directly implies a separation of VP from VNP. We will mainly discuss about two papers. The first one is by Kayal et al. [2015] showing a \Omega ( \sqrt{d/t}) lower bound for writing an explicit univariate degree- d polynomial f (x) as a sum of powers of degree- t polynomials. Then, we will talk about a more recent work by Marco-Koiran [2017] which establishes a "tight" \Omega(d) lower bound for the representation of a family of real univariate polynomials as sums of powers of degree 1 polynomials. Note that, the previous result by Kayal et al. could only give \Omega( \sqrt{d} ) bound. We plan to cover the main result of the papers (with a little bit of background with the connection to proving VP vs VNP from Univariate lower bound) in 2 lectures.

ALL SESSIONS


Contact

Image

Sumanta Ghosh

Head Co-ordinator

Image

Rajendra Kumar

Co-ordinator

Image

Mahesh S R

Co-ordinator