#### 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.