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[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
Room 005 (Ground Floor)