Description du projet de recherche

The $\mathrm{P}$ versus $\mathrm{NP}$ problem is widely recognized as the main open problem in the theory of computing. Given the difficulty of the problem, several  algebraic versions of $\mathrm{P}$ versus $\mathrm{NP}$ have been proposed. The hope is that one can more easily bring  methods from algebra and geometry to bear on these new versions of the problem.  The main goal of this project is to make progress on the $\mathrm{VP}$ versus $\mathrm{VNP}$ problem. This algebraic version of $\mathrm{P}$ versus $\mathrm{NP}$  was put forward by Leslie Valiant at the end of the 70's. In Valiant's model, the focus is on the complexity of polynomial evaluation.

In a nutshell, the algorithmic content of $\mathrm{VP}$ versus $\mathrm{VNP}$ is as follows : can the permanent of a $n\times n$ matrix be evaluated in a number of arithmetic operations which is polynomial in $n$ ? (The permanent polynomial is similar to the determinant, except that there are only positive signs in its expansion as a sum of $n!$ terms.) This question can be formalized using the computation model of arithmetic circuits. It is widely conjectured that it has a  negative answer. We note that, as in classical $\mathrm{NP}$-completeness theory, the permanent can be replaced by any other $\mathrm{VNP}$-complete polynomial in the statement of this problem.

In recent years,$\mathrm{VP}$ versus $\mathrm{VNP}$ has been the object of renewed attention from the complexity theory community. A central goal of the project is to contribute to this effort by developing proof techniques which may eventually lead to a resolution of this problem ; and to obtain lower bounds for restricted classes of arithmetic circuits which will pave the way toward this goal. We will also keep an eye on problems that are directly connected to arithmetic circuit lower bounds such as the derandomization of polynomial identity testing.

A second research direction is the study of structural properties of arithmetic circuits. As an example of such a property, one may cite the classical parallelization results from the 70's and 80's and the more recent results on ``reduction to depth four'' (first obtained by Agrawal and Vinay, and then refined by Koiran and Tavenas). Another  family of examples is given by the characterization of algebraic complexity classes by various types of arithmetic circuits (multiplicatively disjoint circuit, skew and weakly skew circuits, arithmetic branching programs...) as in the work of Toda and Malod. Structural results are interesting in their own right, and can also play a role in lower bound results as shown by the recent work on depth 4 circuits.