Abstract Lecture 3:

How many arithmetic operations (additions and multiplications) does it take to evaluate a given polynomial? Even extremely crude estimates for natural polynomials are extraordinarily hard to get.

For example, it is well known that while the determinant of an nxn matrix has superexponentially many monomials (exactly n!), it can be computed using n^3 operations (yes, division is not necessary). Can the same be done for the permanent of a matrix (the sibling of determinant without the signs)?

For another example, the univariate polynomial x^n, despite having degree n, can be computed using 2\log n operations. Can the same be done to the degree-n polynomial (x+1)(x+2)...(x+n) ?

I will survey results and open questions in this vast field. I will also explain some remarkable connections, e.g. why a positive answer in the first example implies that P=NP, and why a positive answer in the second example implies an ultrafast integer factorization algorithm (and hence breaking the numerous cryptographic systems based on factoring).