Homework 2

This homework covers the material from lectures 6 to 12.

Due date: June 24th, 10pm Waterloo time.

LaTeX template, in case you want to write it in LaTeX.

Required Exercises

Problem 1 - Depth Reduction (25 points)

In this exercise, we will prove another useful depth reduction theorem for algebraic formulas: the log-product decomposition.

Prove the following depth-reduction claim:

Let $\mathrm{\Phi }$ be a homogeneous algebraic formula of size $s$ computing a form $f$ of degree $d$. Then, $f$ can be written as a sum of $s+1$ log-product forms, that is, $$f=\sum _{i=0}^s{f}_i,$$ where for each $0\le i\le s$, we have $$f_i=\prod _{j=1}^{\ell }{g}_{i,j},$$ where

• each $g_{i,j}$ is a form
• $(1/3{)}^j\cdot d\le \mathrm{deg}(g_{i,j})\le (2/3{)}^j\cdot d$
• $g_{i,\ell }=1$

Hint: Like Brent’s depth reduction, find a gate $v$ in $\mathrm{\Phi }$ whose degree is at least $d/3$ and at most $2d/3$.

Problem 2 - Lower Bounds for an easy polynomial (25 points)

Let $\mathrm{\Sigma }{\wedge }^d\mathrm{\Sigma }$ denote the class of degree $d$ forms that can be computed by sums of $d$ powers of linear forms. That is, a polynomial $f$ is in $\mathrm{\Sigma }{\wedge }^d\mathrm{\Sigma }$ if there are linear forms $L_1,\dots ,L_s$ such that $$f=L_1^d+\cdots +L_s^d=\sum _{i=1}^s{L}_i^d.$$ The size of a $\mathrm{\Sigma }{\wedge }^d\mathrm{\Sigma }$ circuit is the top fanin of the circuit, that is, the number of powers of linear forms in the sum.

Prove that if a circuit from $\mathrm{\Sigma }{\wedge }^n\mathrm{\Sigma }$ of size $s$ computes the monomial $x_1\cdots x_n$, then $s=2^{\mathrm{\Omega }(n)}$.

Remark: given a degree $d$ form $f$, the minimum number of powers of linear forms needed to compute $f$ is called the Waring rank of $f$.

Problem 3 - Lower Bounds (25 points)

In the first homework, we saw that any elementary symmetric polynomial on $n$ variables can be computed by a $\mathrm{\Sigma }\mathrm{\Pi }\mathrm{\Sigma }$ circuit with top fanin $O(n)$. A much harder question is to prove that such a representation is in a sense optimal.

As a first step towards this goal, prove that for $d=n/10$, any representation of $E{S}_d(x_1,\dots ,x_n)$ as a $\mathrm{\Sigma }\mathrm{\Pi }\mathrm{\Sigma }$ circuit must have top fanin $\mathrm{\Omega }(n)$.

Hint: consider what happens when you restrict the variables to be in a hyperplane, i.e., some linear combination of the variables is zero.

Problem 4 - Shifted Partials of the Determinant (25 points)

We will prove that the shifted partial derivatives of the determinant have large enough dimension. Let $X=(x_{i,j})$ be an $n\times n$ symbolic matrix.

More precisely, we will show that for any $k,\ell \ge 0$, $$\mathrm{\Delta }(k,\ell ):=\dim (\text{span}\{X^{\ell }{\partial }^{k}det(X)\})\ge (\genfrac{}{}{0ex}{}{n+k}{2k})\cdot (\genfrac{}{}{0ex}{}{(n-1{)}^2+2(n-k)+\ell -2}{\ell }).$$

To do this, we will simply look at how many distinct leading monomials we can get by taking the shifted partial derivatives of the determinant.

Let us use the following monomial ordering on the variables $x_{i,j}$: $$x_{1,1}\succ x_{1,2}\succ \cdots \succ x_{1,n}\succ x_{2,1}\succ \cdots \succ x_{n,n}.$$ We extend this ordering to monomials by lexicographically ordering the monomials in the variables $x_{i,j}$.

1. Prove that any $k^{th}$ partial derivative of the determinant is either zero or is an $(n-k)\times (n-k)$ minor of $X$.

2. Using the monomial ordering above, if $S:=\{i_1,\dots ,i_r\}$ and $T:=\{j_1,\dots ,j_r\}$ are two sets of $r$ distinct indices, $1\le i_1<\cdots <i_r\le n$, $1\le j_1<\cdots <j_r\le n$, show that the leading monomial of the $(S,T)$-minor of the determinant is $x_{i_1,j_1}\cdots x_{i_r,j_r}$.

Now we would like to say that such leading monomials will yield many distinct leading monomials when we apply the “shifts” (i.e. multiply by distinct monomials of degree $\ell$). For this purpose, define an $r$-increasing monomial to be a monomial of the form $x_{i_1,j_1}\cdots x_{i_r,j_r}$ where $1\le i_1<\cdots <i_r\le n$, $1\le j_1<\cdots <j_r\le n$.

Note that the leading monomial of the $(S,T)$-minor of the determinant is an $r$-increasing monomial.

3. Prove that $$\mathrm{\Delta }(k,\ell )\ge |\{\text{monomials of degree }\ell +n-k\text{ that are multiples of an }(n-k)\text{-increasing monomial}\}|.$$

With the above result, it is enough to bound the number of monomials of degree $\ell +n-k$ that are multiples of an $(n-k)$-increasing monomial. However, we cannot simply multiply the number of $(n-k)$-increasing monomials by the number of monomials of degree $\ell$, as we will be overcounting. Thus we will count only a subset of these monomials (just as [GKKS'14]).

Definition (canonical increasing sequence): Let $D_2=\{x_{i,i},x_{i,i+1}\mid 1\le i<n\}\cup \{x_{n,n}\}$. This is the set of variables that appear in the diagonal and right above the diagonal of the matrix $X$. For any monomial $m$ let the canonical increasing sequence of $m$, denoted by $CIS(m)$, to be the largest (in the monomial ordering $\succ$) $(n-k)$-increasing monomial that divides $m$ and is formed by variables in $D_2$. If $m$ is not divisible by any $(n-k)$-increasing monomial formed by variables in $D_2$, then $CIS(m)=1$.

4. Prove the following claim: let $p$ be an $(n-k)$-increasing monomial formed by variables in $D_2$. Then, there are at least $2(n-k)-1$ variables in $D_2$ such that if $\mu$ is any monomial in these variables, then $CIS(p\mu )=p$.

5. Using the above claim, prove that $$\mathrm{\Delta }(k,\ell )\ge (\genfrac{}{}{0ex}{}{n+k}{2k})\cdot (\genfrac{}{}{0ex}{}{(n-1{)}^2+2(n-k)+\ell -2}{\ell }).$$

Hint: compute the number of $(n-k)$-increasing monomials formed by variables in $D_2$, and note that you can multiply each of these monomials any monomial of degree $\ell$ in the “good variables” (i.e. variables that don’t change the CIS).