Upcoming Talk

ArithmeticCircuit

Title

Speaker

Date

Time

Venue

Abstract

Lower Bounds for Univariate Polynomials - 2

Pranjal Dutta

14st March 2019

3:30-4:30 PM

KD103

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.

Who are we???

SIGTACS - Special Interest Group on Theoretical Aspects of Computer Science, was born out of an effort to bring together people interested in areas of Theoretical Computer Science.


What we do???

It is a platform for students and faculty members to come together and share their excitement in the area. The group aims at organizing problem solving sessions, seminars and guest lectures.

What we like???

Algorithms, Combinatorics, Cryptology, Quantum Computing, Graph-Theory, Information Theory, Game-Theory, Computational Complexity.


Contact

Image

Sumanta Ghosh

Head Co-ordinator

Image

Rajendra Kumar

Co-ordinator

Image

Mahesh S R

Co-ordinator