License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2019.47
URN: urn:nbn:de:0030-drops-101402
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10140/
Go to the corresponding LIPIcs Volume Portal

Bläser, Markus ; Jindal, Gorav

On the Complexity of Symmetric Polynomials

pdf-format:
LIPIcs-ITCS-2019-47.pdf (0.5 MB)

Abstract

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.
In this paper, 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 != 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.

BibTeX - Entry

@InProceedings{blser_et_al:LIPIcs:2018:10140,
  author =	{Markus Bl{\"a}ser and Gorav Jindal},
  title =	{{On the Complexity of Symmetric Polynomials}},
  booktitle =	{10th Innovations in Theoretical Computer Science  Conference (ITCS 2019)},
  pages =	{47:1--47:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{124},
  editor =	{Avrim Blum},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10140},
  URN =		{urn:nbn:de:0030-drops-101402},
  doi =		{10.4230/LIPIcs.ITCS.2019.47},
  annote =	{Keywords: Symmetric Polynomials, Arithmetic Circuits, Arithmetic Complexity, Power Series, Elementary Symmetric Polynomials, Newton's Iteration}
}

Keywords: Symmetric Polynomials, Arithmetic Circuits, Arithmetic Complexity, Power Series, Elementary Symmetric Polynomials, Newton's Iteration
Collection: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Issue Date: 2018
Date of publication: 08.01.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI