Lower hounds in the algebraic computational complexity

This paper is a survey on some selected methods for obtaining lower bounds in the algebraic complexity. The content is the following.
Introduction. 1. Basic notions
Chapter I. Algebraic-geometric approach to obtaining lower bounds of computational complexity of polynomials. 2. Evaluating of a polynomial with “general” coefficients. 3. Computational complexity of the individual polynomials. 4. The degree method and its generalizations (the case of an infinite ground field). 5. The degree method (the case of a finxte ground field) 6. Additive complexity and real roots.
Chapter II. Lower bounds on the multiplicative complexity for the problems in the linear algebra. 7. Multiplicative complexity and the rank. 8. Rank of a pair of bilinear forms. 9. Multiplicative complexity of a bilinear form over a commutative ring. 10. Bounds on the rank of algebras. 11. Linearized multiplicative complexity.
Chapter III. Complexity for straight-line programs of nonstandard kinds. 12. Irrational computational complexity of algebraic functions. 13. Monotone programs. 14. Time-space tradeoffs. 15. Graph-theoretic methods in the algebraic complexity. 16. Additive complexity in triangular and directed computations and Bruhat decomposition.
We shall explain in more detail the author's results from $\S\S$6, 11, 15, 16 unpublished earlier.
In $\S$6 the best previous known bound on the additive complexity over the real numbers in the terms of the number of real roots ([26]) is essentially improved. Namely, let polynomials $g_1,\dots g_n\in\mathbb R[x_1,\dots,x_n]$ and the system $g_1=\dots=g_n=0$ have $N$ pairwise distinct discrete simple real roots. Then Corollary 6.2. The additive complexity of a set $\{g_1,\dots g_n\}$ is greater than $(\sqrt{\log N}-2n)/3$.
The proof is based on one Hovansky theorem [21]. This bound is sharp up to taking of the square root according to [63].
In $\S$11 the following invariant $C_l(f)$ of the homogenuous form $f$ of the degree $d_1$ over $n$ variables $x_1,\dots, x_n$ is introduced:
$$ C_l(f)=\min\left\{N:f=\sum_{1\leqslant i\leqslant N}l_1^{(i)}\dots l_{d_1}^{(i)}, \text{ where }l_j^{(i)}\text{ is a linear form } (1\leqslant i\leqslant N, 1\leqslant j\leqslant d_1)\right\}. $$
This definition is similar in spirit to the definition of the tensor rank (see e. g. [54]). We suggest a method for obtaining lower bounds for $C_l(f)$.
For the convenience of notations (w.l.o.g.) we assume that $d_1=2d$ is even. Consider the auxiliary matrices $A$ of the size $n^d\times n^d$ the rows and columns of which are numbered by the vectors of the form $I=(i_1,\dots,i_d)$ for all $1\leqslant i_1\dots i_d\leqslant n$. То each vector $I$ there corresponds a monomial $x^I=x_{i_1}\dots x_{i_d}$ of degree $d$. By $|I|$ we denote the number $k_1!\dots k_n!$, where $k_i$ is the number of $j$ such that $i_j=i$. To every matrice $A$ there corresponds the form $g_A=\sum_{I, J}a_{I, J}x^Ix^J$ of degree $d_1=2d$. Finally, we define a linear operator $L$ on the matrices of the size $n^d\times n^d$ by the formula: $L(A)=B$, where an entry
$$ b_{P, Q}=\left(\sum_{x^Px^Q=x^K=x^Ix^J}a_{I, J}\right)|K|. $$
A form $g_A=0$ iff $L(A)=0$, so $L(f)$, which can be defined as $L(A)$ for any $A$ such that $f=g_A$, is an invariant of the form $f$.
Theorem 11.3. $C_l(f)\geqslant(rgL(f))/d_1!$
As a corollary we obtain for example that
$$ C_l\left(\left(\sum_{1\leqslant i\leqslant n}x_i\bar{x_i}\right)^d\right)\geqslant{n+d-1\choose n-1}/(2d)! $$

In $\S$15 we consider a class of straight-line programs $\beta$ which satisfy the following restriction (7): for any vertex $v$ of the ordered graph $G_\beta$ corresponding to $\beta$ in the usual manner, the subgraph $T_v$ consisting of all the vertices situated in $G_\beta$ above the vertex $v$ is a tree. From the other hand we allow an initial variable to be represented by more than one initial vertices in $G_\beta$. We say, that a set of the functions $\{g_1,\dots,g_m\}$ is $(\theta, \eta)$-sераrated if after the deleting from the graph $G_\beta$ (for any straight-line program $\beta$ computing $\{g_1,\dots,g_m\}$ satisfying the restriction (7)) of arbitrary $\theta$ vertices, there exist $\eta$ pairs of vertices such that one member of each pair is an initial vertex and the other is a terminal one and between the members of each pair there is some path in $G_\beta$ (this path is unique according to restriction (7) above) containing no vertex from the deleted set of $\theta$ vertices (informally speaking, even if one can utilize “free of charge” some $\theta$ auxiliary functions, a lot of the terminal functions depends essentially on many initial variables). This notion is very close to the notion of $(n, \eta(\theta))$-grate ([60]) and was actually introduced independently in [6]. The following theorem can be considered as a kind of weakened answer on the problem of Valiant posed in [60], and one can find in fact the method for proving of the theorem in [6].
Theorem 15.1. For any $(\theta, \eta)$-separated set $\{g_1,\dots, g_m\}$ the complexity of every straight-line program $\beta$ satisfying the restriction (7) and computing $\{g_1,\dots, g_m\}$ is greater than a number $M$, where $M$ is an unique positive solution of the equation
$$ M=(\eta/m)^{\left(1+\frac{\theta}{M\log 2}\right)}. $$

In the last $\S$16 we introduce two classes of straight-line linear programs (they are called triangular and directed). Every linear program can be represented informally as a sequence of elementary matrix transformations. A triangular program consists of instructions of the form
$$ z_j=:z_j+\alpha z_i,\quad \text{where } i\geqslant j, \alpha\in F. $$
The triangular complexity $C_\Delta$ counts the number of all the instructions. A method for obtaining nonlinear lower bounds on $C_\Delta$ is suggested. For example, set
$$ A_1=\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix},\quad \dots,\quad A_{n+1}=\begin{pmatrix} A_n & E \\ 0 & A_n \end{pmatrix},\quad \dots, $$
where $E$ is the unit matrix. Then $C_\Delta(A_n)=n2^{n-1}$.
The second class of linear programs under consideration is a class of directed programs. A directed program consists of the instructions of the following two forms:
$$ z_j=:z_j+\alpha z_i,\quad \text{where}\quad i\geqslant j, \alpha\in F \qquad\text{and}\qquad z_{k+1}=:z_{k+1}+\alpha z_k. $$
The directed complexity $C_d$ is the number of instructions only of the second form. For $C_d(A)$ the explicit effective formula is obtained in the terms of the so-called generalized Bruhat decomposition introduced by the author and based on the suitable algebraic apparatus in the Chevalley group theory ([11]). The exposition of the results of §16 in detail can be found in [35]. Also it is noticed in §6 that a direct analogy of theorem of Baur and Stressen [25] about the complexity of the partial derivatives is false for the additive complexity $C_+$. Namely, set $f=x_1\dots x_n+x_1x_2^2\dots x_n^n$, then $C_+(f)=1$ and from the other hand
$$ C_+\left(\frac{\partial f}{\partial x_1},\dots,\frac{\partial f}{\partial x_n}\right)=n $$