文章基本信息

标题：Symmetric Determinantal Representation of Weakly-Skew Circuits
本地全文：下载
作者：Bruno Grenet ; Erich L. Kaltofen ; Pascal Koiran 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2011
卷号：9
页码：543-554
DOI：10.4230/LIPIcs.STACS.2011.543
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：algebraic complexity; determinant and permanent of symmetric matrices; formulas; skew circuits; Valiant's classes