ABP general lowerbound

References:

• (Allender, Wang - On the power of algebraic branching programs of width 2)[https://eccc.weizmann.ac.il/report/2011/083/]
• I modified this proof significantly, hence I cannot vouch for correctness of my thoughts.

Theorem:

For all $k\geq 8$ $\sum_{i=1}^k x_{2i-1}x_{2i} + l(x)$ for any linear form $l(x)$ cannot be computed by an algebraic branching program of width 2.

Preqrequisites:

• Let an SLP on two registers be denoted by $m_1 \dots m_m$.
• Notice that an SLP in general, could set registers to zero which matrices cannot do. We will disregard these type of SLPs and only look at the with matrices.
• A matrix can be of the following types:
  • Inherently non-degenerate: $\det(A)=c$ for $c\in \mathbb{F}\setminus {0}$.
  • Inherently degenerate: $\det(A)=0$.
  • Potentially degenerate: $\det(A)=p$ where $p$ has some polynomial not in the previous cases.

Proof (Theorem 34):

• Intuitively the following should be true:
  • The SLP uses mostly potentially degenerate matrices.
  • Inherently degenerate matrices do not contribute to the computation.
  • Inherently non-degenerate matrices have dimension 1.
• We will ignore the case of inherently degenerate matrices.
• There are two cases for inherently degenerate matrices:
  • Bad: $R_1=c$, $R_2=\alpha \cdot R_1$ where $R_1, R_2$ are the registers (up to permutation). $\begin{pmatrix} 1/R_1& 0\ 1& 0\end{pmatrix}$.
  • Good: Otherwise.

Case 1 - Only potentially degenerate matrices and inherently non-degenerate matrices:

Case 2 - Some inherently degenerate matrices of the good form:

Case 3 - Some inherently degenerate matrices of the bad form:

• We are ignoring this case.