# Colloquium by Gorav Jindal (Aalto University, Helsinki): On the Complexity of Symmetric Polynomials

The fundamental theorem of symmetric polynomials states that for a symmetric polynomial *f*_Sym in **C**[*x*_{1},*x*_{2},...,*x** _{n}*], there exists a unique "witness"

*f*in

**C**[

*y*

_{1},

*y*

_{2},...,

*y*

*] such that*

_{n}*f*_Sym=

*f*(

*e*

_{1},

*e*

_{2},...,

*e*), where the

_{n}*e_*'s are the elementary symmetric polynomials.

_{i}In this work, we study the arithmetic complexity

*L*(

*f*) of the witness

*f*as a function of the arithmetic complexity

*L*(

*f*_Sym) of

*f*_Sym. We show that the arithmetic complexity

*L*(

*f*) of

*f*is bounded by poly(

*L*(

*f*_Sym),deg(

*f*),

*n*). Prior to this work, only exponential upper bounds were known for

*L*(

*f*). The main ingredient in our result is an algebraic analogue of Newton’s iteration on power series.

As a corollary of this result, we show that if VP is not equal to VNP then there are symmetric polynomial families which have super-polynomial arithmetic complexity. This is joint work with Markus Bläser.

### Time & Location

Jan 20, 2020 | 05:00 PM s.t.

Freie Universität Berlin

Institut für Informatik

Takustr. 9

14195 Berlin

Room 005 (Ground Floor)