Grenet, Bruno
[Verfasser:in];
Kaltofen, Erich L.
[Verfasser:in];
Koiran, Pascal
[Verfasser:in];
Portier, Natacha
[Verfasser:in]
;
Bruno Grenet and Erich L. Kaltofen and Pascal Koiran and Natacha Portier
[Mitwirkende:r]
Symmetric Determinantal Representation of Weakly-Skew Circuits
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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.