10.4230/LIPIcs.STACS.2011.543
Grenet, Bruno
Kaltofen, Erich L.
Koiran, Pascal
Portier, Natacha
Symmetric Determinantal Representation of Weakly-Skew Circuits
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
2011
Computer Science
000 Computer science, knowledge, general works
Herbstritt, Marc
2011-03-11
eng
ConferencePaper
12 pages
application/pdf
1.0
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC-BY-NC-ND)
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.