Document

**Published in:** LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Polynomial identity testing and arithmetic circuit lower bounds are two central questions in algebraic complexity theory. It is an intriguing fact that these questions are actually related.
One of the authors of the present paper has recently proposed
a "real tau-conjecture" which is inspired by this connection.
The real tau-conjecture states that the number of real roots of
a sum of products of sparse univariate polynomials should be
polynomially bounded. It implies a superpolynomial lower bound on the
size of arithmetic circuits computing the permanent polynomial.
In this paper we show that the real tau-conjecture holds true for a restricted class of sums of products of sparse polynomials.
This result yields lower bounds for a restricted class of depth-4 circuits: we show that polynomial size circuits from this class cannot compute the permanent, and we also give a deterministic polynomial identity testing algorithm for the same class of circuits.

Bruno Grenet, Pascal Koiran, Natacha Portier, and Yann Strozecki. The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 127-139, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{grenet_et_al:LIPIcs.FSTTCS.2011.127, author = {Grenet, Bruno and Koiran, Pascal and Portier, Natacha and Strozecki, Yann}, title = {{The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)}, pages = {127--139}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-34-7}, ISSN = {1868-8969}, year = {2011}, volume = {13}, editor = {Chakraborty, Supratik and Kumar, Amit}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.127}, URN = {urn:nbn:de:0030-drops-33501}, doi = {10.4230/LIPIcs.FSTTCS.2011.127}, annote = {Keywords: Algebraic Complexity, Sparse Polynomials, Descartes' Rule of Signs, Lower Bound for the Permanent, Polynomial Identity Testing} }

Document

**Published in:** LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

We deploy algebraic complexity theoretic techniques for constructing symmetric determinantal representations of weakly-skew circuits, which include formulas. Our representations produce matrices of much smaller dimensions than those given in the convex geometry literature when applied to polynomials having a concise representation (as a sum of monomials, or more generally as an arithmetic formula or a weakly-skew circuit). These representations are valid in any field of characteristic different from 2. In characteristic 2 we are led to an almost complete solution to a question of Buergisser on the VNP-completeness of the partial permanent. In particular, we show that the partial permanent cannot be VNP-complete in a finite field of characteristic 2 unless the polynomial hierarchy collapses.

Bruno Grenet, Erich L. Kaltofen, Pascal Koiran, and Natacha Portier. Symmetric Determinantal Representation of Weakly-Skew Circuits. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 543-554, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{grenet_et_al:LIPIcs.STACS.2011.543, author = {Grenet, Bruno and Kaltofen, Erich L. and Koiran, Pascal and Portier, Natacha}, title = {{Symmetric Determinantal Representation of Weakly-Skew Circuits}}, booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)}, pages = {543--554}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-25-5}, ISSN = {1868-8969}, year = {2011}, volume = {9}, editor = {Schwentick, Thomas and D\"{u}rr, Christoph}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.543}, URN = {urn:nbn:de:0030-drops-30426}, doi = {10.4230/LIPIcs.STACS.2011.543}, annote = {Keywords: algebraic complexity, determinant and permanent of symmetric matrices, formulas, skew circuits, Valiant’s classes} }