Helsinki Algorithms Seminar: Gorav Jindal "On the Complexity of Symmetric Polynomials"

On the Complexity of Symmetric Polynomials

Gorav Jindal
Aalto University

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]: https://rjlipton.wordpress.com/2009/07/10/arithmetic-complexity-and-symmetry/

Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.

Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.