2026-08-16T23:04:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3042 2024-03-06T10:33:47Z ddc:004 open_access

Symmetric Determinantal Representation of Weakly-Skew Circuits Grenet, Bruno Kaltofen, Erich L. Koiran, Pascal Portier, Natacha algebraic complexity determinant and permanent of symmetric matrices formulas skew circuits Valiant’s classes 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bruno Grenet and Erich L. Kaltofen and Pascal Koiran and Natacha Portier 2011 Is Part Of LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2011.543 urn:nbn:de:0030-drops-30426 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.543 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode