Date: October 18, 2018 16:15–17:00
Place: Konemiehentie 2, Room T4 (Otaniemi)
Speaker: Gorav Jindal

Title : On the Complexity of Symmetric Polynomials

Abstract :It is an easy exercise to show that all symmetric Boolean functions are easy to compute (corresponding language is in the complexity class TC^0). Lipton and Regan ([1]) ask whether the same is also true for symmetric polynomials? They ask whether “Understanding the arithmetic complexity of symmetric polynomials is enough ?” In this work, we answer this question in affirmative.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_n] such that f_sym = f(e_1, e_2, .., e_n), where the e_i’s are the elementary symmetric polynomials.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). To the best of our knowledge, 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 \neq VNP then there exist symmetric polynomial families which have super-polynomial arithmetic complexity.
This is a joint work with Prof. Markus Bläser (Department of Computer Science, Saarland University)
[1] :