Title: The quest for a polynomial that is hard to compute
Speaker: Neeraj Kayal (Microsoft Research, Bangalore)
Date: 06 October 2017
Time: 3 - 4:55 pm (with a 15 minute break in between)
Venue: LH-1, Mathematics Department

We consider the computation of n-variate polynomials over a field F via a sequence of arithmetic operations such as additions, subtractions, multiplications, divisions, etc. It has been known for at five decades now that a random n-variate polynomial of degree n is hard to compute. Yet not a single explicit polynomial is provably known to be hard to compute (although we have a lot of good candidates). In this talk we will first describe this problem and its relationship to the P vs NP problem. We will then describe several partial results on this problem, both old and new, along with a more general approach/framework that ties together most of these partial results.


Contact: +91 (80) 2293 2711, +91 (80) 2293 2625
E-mail: chairman.math[at]iisc[dot]ac[dot]in