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.