Theory Seminar: Interpolation in Valiant's Theory

Abstract:

The following question will be studied: if a polynomial can be evaluated by a polynomial-time (boolean) algorithm, does it have a polynomial-size arithmetic circuit? In other words, do boolean operations decrease computation time, or are additions and multiplications enough?

I will present a recent work with Pascal Koiran on this question which will be linked to open problems in algebraic complexity. In particular, we show that a negative answer to this question implies the separation of the algebraic versions of P and NP in Valiant's model. The method used relies on Lagrange interpolation and on results of Peter Brgisser about the computation of integers in the counting hierarchy. We also give other applications to algebraic complexity.