Border Complexity

Border Complexity

Sources:

• Bringman, Ikenmeyer, Zuiddam - On algebraic branching programs of small width
• Saxena - Diagonal Circuit Identity Testing and Lower Bounds
• Kumar - On top fan-in vs formal degree for depth-3 arithmetic circuits
• Shpilka - Affine Projections of Symmetric Polynomials
• Grochow - Unifying and generalizing known lower bounds via geometric complexity theory

Prerequisites

• Circuits
• ABP
• Formulas

General

• Rank Based lower bounds generally transfer see Grochow.
  • Proof Sketch: Take a matrix $A$ with $\epsilon$. The rank of $A$ can never be smaller than the rank of a matrix $A$ without $\epsilon$.

Bringman, Ikenmeyer, Zuiddam - On algebraic branching programs of small width

Definitions

• Take any complexity measure $L$.
• A polynomial has border complexity $s$ if there exists polynomials $g_1,g_2,\dots$ that converge to $f$ and $L(g_i)$ has complexity bounded by $s$.
• Equivalent: $f$ has complexity $s$ if there exists polynomials $f_1,\dots, f_k$ and integer $k$: $h=f+\varepsilon f_1 + \dots + \varepsilon^k f_k$ and $L(h)<s$ (where we treat $\varepsilon$ as a formal variable in the complexity measure $L$).
  • Notice that the degree of $\varepsilon$ can be large (i.e., exponential).
• As usual, we can define classes of border complexity, using these new measures of complexity.

Previous Knowledge

• Width 3 ABP is equal to formula (Ben-Or, Cleve).
• ABP width 2 is not universal.

Main Theorem

• Theorem: Border of Width 2 ABP can compute Formulas.
• Border of formulas and formulas are the same, i.e., $(\bar VP_e = \bar ABP_2)$ with polynomial size error degree polynomial.

Proof

• Let $Q(f) = \begin{pmatrix} f& 1\ 1& 0\end{pmatrix}$
• We will only show the case where epsilon power is zero where it is not necessary. While technically, all have epsilon power, it is a similar proof.
• Addition ($F+G$): Simulated by $F\cdot Q(0) \cdot G$.
  • $deg(\epsilon)=e_f + e_g$, size=$O(s_f + s_g)$.
  • $\begin{pmatrix} f& 1\ 1&0\end{pmatrix} \cdot \begin{pmatrix} 0& 1\ 1&0\end{pmatrix} \cdot \begin{pmatrix} g& 1\ 1&0\end{pmatrix} = \begin{pmatrix} 1& f\ 1&0\end{pmatrix}\begin{pmatrix} g& 1\ 1&0\end{pmatrix}$.
• Squaring: $\begin{pmatrix} -\epsilon^{-1}& 0\ -1&\epsilon\end{pmatrix} \cdot Q(f) \cdot \begin{pmatrix} \epsilon^2& 1\ -1& 0\end{pmatrix} \cdot Q(f) \cdot \begin{pmatrix} \epsilon^{-1}& 0\ 0& \epsilon\end{pmatrix}$.
  • $deg(\epsilon)=2 e_f + 4$, size= $2O(s_f)$.
  • $= \begin{pmatrix} -f/\epsilon& -1/\epsilon\ -f+\epsilon& -1\end{pmatrix} \cdot \begin{pmatrix} \epsilon^2& 1\ -1& 0\end{pmatrix}\cdot Q(f)\cdot \begin{pmatrix} 1/\epsilon& 0\ 0& \epsilon\end{pmatrix}$
  • $= \begin{pmatrix} -f\epsilon + 1/\epsilon& -f/\epsilon\ -f\epsilon^2 + \epsilon^3+1& -f+\epsilon\end{pmatrix} Q(f)\cdot \begin{pmatrix} 1/\epsilon& 0\ 0& \epsilon\end{pmatrix}$
  • $=\begin{pmatrix} f/\epsilon -f^2\epsilon - f/\epsilon& 1/\epsilon - f\epsilon\ f\epsilon^3 -f^2\epsilon^2 +f - f+k& \epsilon^3 -f\epsilon^2 + 1\end{pmatrix} \cdot \begin{pmatrix} 1/\epsilon& 0\ 0& \epsilon\end{pmatrix}$
  • $=\begin{pmatrix} -f^2& 1-f\epsilon\ f\epsilon^2 - f^2\epsilon + 1& \epsilon^4 -f\epsilon^3+\epsilon\end{pmatrix}$
• Multiplication with constant is the same way as always.
• Multiplication ($f/2 \cdot g$): Use that $-(f/2)^2 + (-g^2) + (f/2 + g)^2 = f\cdot g$.
  • $deg(\epsilon) = 4 e_f + 4 e_g + 12$, size=$O(4s_f + 4s_g)$.
• We need exponential many matrices in the depth of the circuit. Using formula depth reduction gives the result of polynomial size in formula size.
• Rough bound on the $\epsilon$ degree, exponential in the depth of the formula.
• Rough bound on the size, exponential in the depth of the formula.
  • Go up the formula in depth.
  • For every gate, we already have computed the two children and need the new size to compute it.
  • Hence, per depth increase, we get an increase of at most $4s_f + 4s_g + c$.
  • As a formula depth reduction to $\log n$ depth exists, we have polynomial $\epsilon$ degree and polynomial size.
• Notice that ABP of width 2 are not closed under taking homogeneous components.

Kumar - On top fan-in vs formal degree for depth-3 arithmetic circuits

Theorem

• Any homogenous polynomial of degree $d$ can be "approximated" (in the border complexity sense) by a $\Sigma\Pi\Sigma$ circuit with top fan-in $d+1$.
  • The formal degree is $d\cdot 2^d \cdot \binom{n+d-1}{d-1}$.
  • The size is large but the top gate has small fan-in.

Proof

Overview

• We define $sym$ to be the elementary symmetric polynomial.
• Any polynomial $f$ can be computed by $sym(L_1,\dots,L_m)$ for $L_i$ being homogeneous linear forms (here, $m\in exp(O(d))$).
• Hence, $P= homc(\prod_{i\in [m]} L_1+1)$ of degree equal to $d$.
• Hence, extracting approximate homogeneous components with complexity in $d$ and NOT $m$ finishes the proof.

Homogeneous components

• Let $f=\sum_{i\in [d]} f_i(x)$ where $f_i$ has degree equal to $i$. Then there $\sum \beta_{i,j} f(\alpha_{i,j}x) = f_i + R$ where every monomial has degree at least $i+1$.
  • Let $g(y) = f(yx_1,\dots,yx_n)$.
  • $g(y) = \sum_j y^i f_j(x)$.
  • Fix an $i$. Take distinct elements from $\mathbb{F}$, $\alpha_1,\dots,\alpha_i$.
  • Then for every $k$, we have $Q(\alpha_{k}) = \sum_{j=0}^d \alpha_{k}^j f_j(x)$.
  • Let $\gamma_j = (\alpha_j^0, \dots, \alpha_j^i)$.
  • Notice that $\gamma_0,\dots,\gamma_i$ are linearly independent.
  • Hence, there exists $\beta$ such that $\sum_{j=0}^i \beta_{j}\gamma_j = (0,\dots,0,1)$.
  • Hence, $\sum_{j=0}^i \beta_j f(\alpha_j x) = \sum_{j=0} \beta_j \left(\sum_{j'=0}^d \alpha_j^{j'} f_j'(x)\right) = \sum_{j'=0}^d \left(\sum_{j=0}^i \beta_j \alpha_j^{j'} \right) f_{j'}(x)$.
  • With the previous requirement on $\beta,\gamma$ this gives the proof.
  • Notice that this does not say anything about degree higher than $i$ as $\sum_{j}^i \beta_j\gamma_j$ does not have any requirements on $i'>i$.
  • Setting $\alpha' = \alpha\varepsilon$ gives us the approximation. This gives us an $\epsilon^i$ factor but we can divide by it.

Summary

• These two results give us that:
• $VF \subseteq \overline{ABP_2}\subseteq HOM\subseteq \overline{\Sigma\Pi\Sigma}$.

Symmetric Polynomials:

• We are talking about linear projections of symmetric polynomials, i.e., symmetric polynomials of linear forms.
• Universal (exponential in the degree).
• Lower bounds known:
  • $C_{sym}(f) > \sqrt(C_3(f))$ (Symmetric vs depth 3).
  • $C_{sym}(\det_{\sqrt{n}}) \geq 2n-3\sqrt{n}$.

Lower bounds versus depth 3 circuits of Symmetric Polynomial (Shpilka)

• We only show lower bound for $S$ without linear forms, i.e., the symmetric polynomial.
• Why do the lower bounds transfer?
• Does this lower bound transfer?

Theorem 4.3:

• For every $d\geq 2$ and every affine subspace $A$ such that degree of $S_n^d|_A$ is smaller than $d$, $dim(A)\leq $\frac{n+d}{2}$.

Prerequisites to the proof:

• Lemma 5.6: In every vector space of dimension $r$ there is a vector with at least $r$ coordinates that are all 1.
• Definition 5.2: For $v\in C^n$ and a polynomial $f\in C[x_1,\dots,x_n]$ $\partial_v(f) = \sum_{i=1}^n v_i \frac{\partial f}{\partial x_i}$.
• Proposition 5.4:
  • Linear functions: $\partial_v(L)=L(v_1,\dots,v_n$.
  • $\partial_v(fg) = g\partial_v(f) + f\partial_v(g)$.
  • $\partial_v(\prod_{i=1}^t L_i) = \sum_{i=1}^t (L_i(v)\prod_{j\neq i} L_j)$.
• Lemma 5.5: Let $U = { (x_1,\dots,x_k) \mid x_1=\dots = x_k=0}$ and $v such that $v_1=\dots v_{d-1}=1$, $\sum_{i=1}^k v_i =0$ then for every $r\leq d$ $\partial_v(S_k^r(x_1,\dots,x_k))|U = (1-r)S{d-1}^{r01}(x_1,\dots,x_{d-1})$.
• Definition 5.1: For every polynomial $f\in C[x_1,\dots,x_k]$, $\psi(f) = \frac{1}{k!} \sum_{\sigma\in S_k} f(x_{\sigma(1)},\dots,x_{\sigma(k)})$
• Proposition 5.2:
  • $\psi(f)$ is a symmetric polynomial of degree $\leq \deg(f)$.
  • If $g$ is symmetric then $\psi(gf) = g\psi(f)$.
  • $\psi$ is linear.
• Theorem 5.1: Every symmetric polynomial $f$ can be written as a polynomial in $S_m^1,\dots,S_m^m$ (notice that these are algebraically independent).

Proof:

• Let $A$ be given by $x_{k+1} = L_1(x_1,\dots,x_k), \dots, x_{m}=L_{m-k}(x_1,\dots,x_k)$.
• We know that $0=S_m^d|A = \sum{i=0}^d S_k^i(x_1,\dots,x_k) S_{m-k}^{d-i}(L_1,\dots,L_{m-k})$.
• Assume that $k\geq \frac{m+d}{2}$.
• Let $L_0(x_1,\dots,x_k)=x_1+\dots x_k$ and define $V={x \mid L_i(x)=0, 0\leq i\leq m-k}$.
• $dim(V)\geq k-(m-k+1)\geq d-1$
  • $k$ is the dimension of the ambient space, $m-k$ is the dimension of the co-space of $A$, 1 is the extra linear form.
• By Lemma 5.6, there is a vector $v\in V$ with first $d-1$ coordinates one.
• Since $L_i(v)=0$ $\partial_v(S_k^1(x_1,\dots,x_k))=0$ (they are the same) and $\partial_v(S_{m-k}^l(L_1,\dots,L_{m-k}))=0, 1\leq l\leq d$ (as required by $V$).
• By the previous equation, $0=\partial_v(S_k^d(x_1,\dots,x_k)) + \sum_{i=2}^{d-1} \partial_v(S_k^i(x_1,\dots,x_k))S_{m-k}^{d-i}(L_1,\dots,L_{m-k})$ (again by definition of $V$)
• Let $U={ (x_1,\dots,x_k)\in V\mid x_d = x_{d+1} = \dots = x_k =0 }.
• With Lemma 5.5 and Proposition 5.2: $\partial_v(S_k^r(x_1,\dots,x_k))|U = (1-r)S{d-1}^{r-1}(x_1,\dots,x_{d-1})$.
• We can now restrict the previous equation to $U$, resulting in: $0=(1-d)S_{d-1}^{d-1}(x_1,\dots,x_k) + \sum_{i=2}^{d-1} (1-i) S_{d-1}^{i-1}(x_1,\dots,x_{d-1} S_{m-k}^{d-i}(L_1,\dots,L_{m-k})|_U)$.
• Applying $\psi$ to this, gives us: $0=(1-d)S_{d-1}^{d-1}(x_1,\dots,x_{d-1}) + \sum_{i=2}^{d-1} (1-i)S_{d-1}^{i-1}(x_1,\dots,x_{d-1}) \psi(S_{m-k}^{d-1}(L_1,\dots,L_{m-k})_U)$.
• For $1\leq i\leq d-2$ $\psi(S_{m-k}^i(L_1,\dots,L_{m-k})|U)$ is a symmetric polynomial of degree at most $d-2$ and hence can be written as a polynomial in $S{d-1}^1(x_1,\dots,x_{d-1}),\dots,S_{d-1}^{d-2}(x_1,\dots,x_{d-1})$.
• Hence $0=(1-d)S_{d-1}^{d-1} + Q(S_{d-1}^1,\dots,S_{d-1}^{d-2})$ for some polynomial $Q$.
• By Theorem 5.1 all these symmetric polynomials are algebraicaly independent and $1-d$ is not 0. Hence a contradiction.

Theorem 4.5:

• $C_3(Sym_n^d)= \Omega(dn-d^2)$.

Proof:

• We denote by $M_1,\dots,M_r$ the multipication gates with degree at least $d$ in the $\Sigma\Pi\Sigma$ circuit.
• As every gate can have at most $d$ inputs, it suffices to show that $r<\frac{n-d}{2}$.
• Claim: There is an affine subspace $A$ such that $\forall i, M_{i}|_A$ is a constant and $\dim(A)>\frac{n+d}{2}$.
• Look at $S_n^d|_A$ computed by $C$ of $\Sigma\Pi\Sigma$. This circuit under $A$ has now all multiplication gates constant or degree smaller than $d$.
• Hence $S_n^d|_A$ has small degree.
• This is a contradiction by the first theorem.

Shpilka - Affine linear form lower bound

• Lemma: Given a lower bound for any affine subspace of dimension $g(m)$ that $S_m|_A=0$ and $f$ has a subspace of dimension $D$ such that $f|_B=0$ then $g(sym_complexity(f)))\geq D$ ($f$ has to fulfill that it cannot be represented as a polynomial of less than $n$ linear forms.).
• Any subspace that has $f|_B=0$ also reduces the degree of $f$.
• Theorem: For every affine subspace such that $\deg(S|_A)<d$ we have $\dim(A)<\max(m-d, d-1)$.
  • Proof:
  • Assume we have a subspace $A$ such that $S_m^d|_A=$ and $dim(A)=k>m\max(m-d,d-1)$.
  • Write it in linear forms depending on $x_1,\dots,x_k$.
  • Now we can rewrite the symmetric polynomial into $S^j(x_1,\dots,x_k)\cdot S^{d-j}(L_1,\dots,L_{m-k})$.
  • We know the sum is zero by our assumption.
  • Use the permutation operator on this, as it is linear we know the overall polynomial can be written as:
  • $0=S^d(x_1,\dots,x_k) + Q(S^1,S^2,\dots,S^{d-1})$.
  • Hence, $S^1,\dots,S^d$ are algebraic dependent but they are in fact not. This is a contradiction.
• Lower bound theorem
  • By the above theorem, we have a subspace that reduces that degree, hence any subspace reducing to zero has dimension at most $\max(m-d, d-1)$.
  • A subspace $B$ of dimension $D$ that is zero for a target polynomial $f$.
  • Then $sym_complexity(f) - \deg(f) \geq D$ by the lemma.

Others

• Symmetric Polynomial might lie between these classes.
• The lower bound doesn't seem to imply anything so far.