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

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

The fundamental theorem of symmetric polynomials states that for a symmetric polynomial f_Sym in C[x1,x2,...,xn], there exists a unique "witness" f in C[y1,y2,...,yn] such that f_Sym=f(e1,e2,...,en), where the e_i's are the elementary symmetric polynomials.
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)

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)