Symmetric Determinantal Representation of Weakly-Skew Circuits

Bruno Grenet (1, 2) , Erich Kaltofen (3) , Pascal Koiran (1, 2) , Natacha Portier (1, 2)

1 LIP - Laboratoire de l'Informatique du Parallélisme
2 DCS - Department of Computer Science [University of Toronto]
3 Department of Mathematics

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 Bürgisser 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.

Mots clés: algebraic complexity; determinant and permanent of symmetric matrices; formulas; skew circuits; Valiant's classes

Domaines: Complexité [cs.CC]; Algorithme et structure de données [cs.DS]

Bruno Grenet, Erich Kaltofen, Pascal Koiran, Natacha Portier. Symmetric Determinantal Representation of Weakly-Skew Circuits. Symposium on Theoretical Aspects of Computer Science (STACS2011), Mar 2011, Dortmund, Germany. pp.543-554, ⟨10.4230/LIPIcs.STACS.2011.543⟩. ⟨hal-00573631⟩