Towards new lower bounds in algebraic complexity – VONBICA

The P=NP problem is generally considered as one of the major problems in fundamental computer science. The difficulty of obtaining progress on this problem encouraged the researchers to focus on its variants. One of them emerges in arithmetic complexity: can we prove that some explicit polynomials can not be computed by performing only a polynomial number of arithmetic operations? The hope is that the robustness of algebraic structures and the various mathematical tools related to them can help to face these questions.
The analog of Cook's conjecture in this area is the question whether VP=VNP. More explicitly, we want to know if there exists a polynomial-sized sequence of circuits to compute the Permanent (this polynomial can be obtained from the determinant by replacing all subtractions by additions). The question is meaningful since Valiant showed that if the permanent can be computed by small circuits, then this is also the case for any VNP polynomial (i.e., any polynomial whose coefficient bits can be computed efficiently). It is widely conjectured that this existence should not be possible (this would otherwise imply that P=NP in the non-uniform Boolean framework). This question, posed by Valiant as early as 79 [Val79] still remains largely open. However, compared to its Boolean counterpart, many promising results have appeared in recent years as steps towards the hope of its resolution. The central goal of this project is to participate in the advance of these results.