On the complexity of symmetric polynomials

Markus Bläser, Gorav Jindal

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

2 Citations (Scopus)
84 Downloads (Pure)

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.

Original languageEnglish
Title of host publication10th Innovations in Theoretical Computer Science, ITCS 2019
EditorsAvrim Blum
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages1-14
ISBN (Electronic)9783959770958
DOIs
Publication statusPublished - 1 Jan 2019
MoE publication typeA4 Article in a conference publication
EventInnovations in Theoretical Computer Science Conference - San Diego, United States
Duration: 10 Jan 201912 Jan 2019
Conference number: 10

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume124
ISSN (Print)1868-8969

Conference

ConferenceInnovations in Theoretical Computer Science Conference
Abbreviated titleITCS
Country/TerritoryUnited States
CitySan Diego
Period10/01/201912/01/2019

Keywords

  • Arithmetic circuits
  • Arithmetic complexity
  • Elementary symmetric polynomials
  • Newton’s iteration
  • Power series
  • Symmetric polynomials

Fingerprint

Dive into the research topics of 'On the complexity of symmetric polynomials'. Together they form a unique fingerprint.

Cite this