On the complexity of symmetric polynomials

Markus Bläser, Gorav Jindal

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

4 Sitaatiot (Scopus)
114 Lataukset (Pure)

Abstrakti

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.

AlkuperäiskieliEnglanti
Otsikko10th Innovations in Theoretical Computer Science, ITCS 2019
ToimittajatAvrim Blum
KustantajaSchloss Dagstuhl-Leibniz-Zentrum für Informatik
Sivut1-14
ISBN (elektroninen)9783959770958
DOI - pysyväislinkit
TilaJulkaistu - 1 tammik. 2019
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInnovations in Theoretical Computer Science Conference - San Diego, Yhdysvallat
Kesto: 10 tammik. 201912 tammik. 2019
Konferenssinumero: 10

Julkaisusarja

NimiLeibniz International Proceedings in Informatics, LIPIcs
KustantajaSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Vuosikerta124
ISSN (painettu)1868-8969

Conference

ConferenceInnovations in Theoretical Computer Science Conference
LyhennettäITCS
Maa/AlueYhdysvallat
KaupunkiSan Diego
Ajanjakso10/01/201912/01/2019

Sormenjälki

Sukella tutkimusaiheisiin 'On the complexity of symmetric polynomials'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä