Symmetric Determinantal Representation of Formulas and Weakly Skew Circuits

Abstract : We deploy algebraic complexity theoretic techniques for constructing symmetric determinantal representations of formulas and weakly skew circuits. 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.
Type de document :
Chapitre d'ouvrage
Leonid Gurvits, Philippe Pebay, J. Maurice Rojas, David Thompson. Randomization, Relaxation, and Complexity in Polynomial Equation Solving, Amer. Math. Soc., pp.61-96, 2011, Contemporary Mathematics, 978-0-8218-5228-6. 〈10.1090/conm/556〉
Liste complète des métadonnées

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00504925
Contributeur : Bruno Grenet <>
Soumis le : lundi 24 octobre 2011 - 17:13:23
Dernière modification le : mercredi 10 octobre 2018 - 21:28:02
Document(s) archivé(s) le : mercredi 25 janvier 2012 - 02:40:25

Fichiers

preprint111024.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Bruno Grenet, Erich Kaltofen, Pascal Koiran, Natacha Portier. Symmetric Determinantal Representation of Formulas and Weakly Skew Circuits. Leonid Gurvits, Philippe Pebay, J. Maurice Rojas, David Thompson. Randomization, Relaxation, and Complexity in Polynomial Equation Solving, Amer. Math. Soc., pp.61-96, 2011, Contemporary Mathematics, 978-0-8218-5228-6. 〈10.1090/conm/556〉. 〈ensl-00504925v4〉

Partager

Métriques

Consultations de la notice

175

Téléchargements de fichiers

92