On the complexity of symmetric polynomials
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Authors
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
10th Innovations in Theoretical Computer Science, ITCS 2019, pp. 1-14, Leibniz International Proceedings in Informatics, LIPIcs ; Volume 124
Abstract
The fundamental theorem of symmetric polynomials states that for a symmetric polynomial fSym ∈ C[x1, x2, . . ., xn], there exists a unique “witness” f ∈ C[y1, y2, . . ., yn] such that fSym = f(e1, e2, . . ., en), where the ei’s are the elementary symmetric polynomials. In this paper, we study the arithmetic complexity L(f) of the witness f as a function of the arithmetic complexity L(fSym) of fSym. We show that the arithmetic complexity L(f) of f is bounded by poly(L(fSym), 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 6= VNP then there exist symmetric polynomial families which have super-polynomial arithmetic complexity. Furthermore, we study the complexity of testing whether a function is symmetric. For polynomials, this question is equivalent to arithmetic circuit identity testing. In contrast to this, we show that it is hard for Boolean functions.Description
| openaire: EC/H2020/759557/EU//ALGOCom
Other note
Citation
Bläser, M & Jindal, G 2019, On the complexity of symmetric polynomials. in A Blum (ed.), 10th Innovations in Theoretical Computer Science, ITCS 2019., 47, Leibniz International Proceedings in Informatics, LIPIcs, vol. 124, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-14, Innovations in Theoretical Computer Science Conference, San Diego, California, United States, 10/01/2019. https://doi.org/10.4230/LIPIcs.ITCS.2019.47