Algebraic Complexity – CompA

In the VP versus VNP problem, the underlying model of computation is algebraic since the basic operations are the arithmetic operations (addition and multiplication). By contrast, traditional models of computation are boolean: they are based on boolean operation such as the logical AND, OR, NOT.... We plan to make use of the algebraic nature of this model to develop new lower bound methods (which make it possible to show that a problem cannot be solved efficiently in our model). For this purpose we plan to use classical lower bound tools such as combinatorics and linear algebra, but also algebraic tools (e.g. representation theory) and geometric tools (algebraic geometry, or even convex geometry).

Here are two of the results obtained during the first 18 monhs of the project:

- We obtained optimal lower bounds for elementary symmetric polynomials of small degree. This result is based on the method of «shifted partial derivatives« and extend the results obtained by Nisan and Wigderson in the 1990's.

- We proposed to study a simple model of computation: sums of powers of low degree univariate polynomials. We view this model as a «test bed« on wich we can try out new lower bound ideas in a fairly simple setting.

We plan to develop lower bound methods that go beyond the currently most successful method, namely, the method of shifted partial derivatives. We plan to try our ideas on the above-mentioned univariate model. Techniques based on polynomial interpolation look espcially promising.

During the first 18 months of the project we published 3 journal articles and 4 articles in conference proceedings. The complete list of our publications is available from the project's web site.

The P versus 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 P versus NP have been proposed. The hope is that one can bring more easily 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 VP versus VNP problem. This algebraic version of P versus NP was put forward by Leslie Valiant at the end of 1970's. In Valiant's model, the focus is on the complexity of polynomial evaluation.
In a nutshell, the algorithmic content of VP versus 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 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 NP-completeness theory, the permanent can be replaced by any other VNP-complete polynomial in the statement of this problem.

In recent years, VP versus 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). 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 Agrawal-Vinay and Koiran.