On the complexity of symmetric polynomials

Markus Bläser; Gorav Jindal

doi:10.4230/LIPIcs.ITCS.2019.47

On the complexity of symmetric polynomials

Markus Bläser, Gorav Jindal

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

2 Citations (Scopus)

84 Downloads (Pure)

Abstract

The fundamental theorem of symmetric polynomials states that for a symmetric polynomial f_Sym ∈ C[x₁, x₂, . . ., x_n], there exists a unique “witness” f ∈ C[y1, y2, . . ., y_n] such that f_Sym = f(e₁, e₂, . . ., 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 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 language	English
Title of host publication	10th Innovations in Theoretical Computer Science, ITCS 2019
Editors	Avrim Blum
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages	1-14
ISBN (Electronic)	9783959770958
DOIs	https://doi.org/10.4230/LIPIcs.ITCS.2019.47
Publication status	Published - 1 Jan 2019
MoE publication type	A4 Article in a conference publication
Event	Innovations in Theoretical Computer Science Conference - San Diego, United States Duration: 10 Jan 2019 → 12 Jan 2019 Conference number: 10

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume	124
ISSN (Print)	1868-8969

Conference

Conference	Innovations in Theoretical Computer Science Conference
Abbreviated title	ITCS
Country/Territory	United States
City	San Diego
Period	10/01/2019 → 12/01/2019

Keywords

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

Access to Document

10.4230/LIPIcs.ITCS.2019.47

LIPIcs-ITCS-2019-47Final published version, 484 KBLicence: CC BY

Cite this

@inproceedings{c369eb4cc951460ead3b907946c99d89,

title = "On the complexity of symmetric polynomials",

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{\textquoteright}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{\textquoteright}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.",

keywords = "Arithmetic circuits, Arithmetic complexity, Elementary symmetric polynomials, Newton{\textquoteright}s iteration, Power series, Symmetric polynomials",

author = "Markus Bl{\"a}ser and Gorav Jindal",

note = "| openaire: EC/H2020/759557/EU//ALGOCom ; Innovations in Theoretical Computer Science Conference, ITCS ; Conference date: 10-01-2019 Through 12-01-2019",

year = "2019",

month = jan,

day = "1",

doi = "10.4230/LIPIcs.ITCS.2019.47",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

pages = "1--14",

editor = "Avrim Blum",

booktitle = "10th Innovations in Theoretical Computer Science, ITCS 2019",

address = "Germany",

}

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 fur Informatik GmbH, Dagstuhl Publishing, 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

On the complexity of symmetric polynomials. / Bläser, Markus; Jindal, Gorav.

10th Innovations in Theoretical Computer Science, ITCS 2019. ed. / Avrim Blum. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. p. 1-14 47 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 124).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

TY - GEN

T1 - On the complexity of symmetric polynomials

AU - Bläser, Markus

AU - Jindal, Gorav

N1 - Conference code: 10

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

KW - Arithmetic circuits

KW - Arithmetic complexity

KW - Elementary symmetric polynomials

KW - Newton’s iteration

KW - Power series

KW - Symmetric polynomials

UR - http://www.scopus.com/inward/record.url?scp=85069506884&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ITCS.2019.47

DO - 10.4230/LIPIcs.ITCS.2019.47

M3 - Conference contribution

AN - SCOPUS:85069506884

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 1

EP - 14

BT - 10th Innovations in Theoretical Computer Science, ITCS 2019

A2 - Blum, Avrim

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - Innovations in Theoretical Computer Science Conference

Y2 - 10 January 2019 through 12 January 2019

ER -

On the complexity of symmetric polynomials

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this