SPEAKER: Natacha Portier

Laboratoire de
l'Informatique du Parallélisme, ENS Lyon, France; DCS, UofT

TITLE:

Expressing a polynomial as a determinant
ABSTRACT:

In his seminal paper (Completeness classes in algebra,
STOC 1979) Valiant expressed the polynomial computed by an arithmetic formula
as the determinant of a matrix whose entries are constants or variables.

Malod and Toda showed how to express a more general class
of circuits, named weakly-skew circuits by Toda, as a determinant. We are
interested here in expressing formulas and skew circuits as determinant of
symmetric matrices. This question is related to the Lax conjecture.

In my talk I will explain some of these constructions, which 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 field of characteristic 2 unless the
polynomial hierarchy collapses.

Related paper: http://arxiv.org/abs/1007.3804