Homework 1

This homework covers the material from lectures 1 to 5.

Due date: May 27th, 10pm Waterloo time.

PDF version of Homework 1.

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

Required Exercises

Problem 1 - Simulations Between Classses (20 points)

Part 1 (10 points)

Prove that any algebraic formula $\Phi$ of size $s$ can be simulated by an ABP of size $O(s)$.

Part 2 (10 points)

Prove that an ABP of size $s$ can be simulated by a circuit of size $\mathrm{poly}(s)$.

Problem 2 - Another Proof that Permanent in VNP (20 points)

In this question we will study the complexity of certain polynomials with $\{ 0,1 \}$ coefficients.

1. Given a 3-CNF formula $\Phi$ over the boolean variables $w_1,\ldots, w_n$, define the polynomial $f_{\Phi}(x_1, \ldots, x_n)$ as the polynomial whose coefficient of the monomial $x_1^{w_1} \cdots x_n^{w_n}$ equals $\Phi(w_1, \ldots, w_n)$.

Prove that $f_{\Phi} \in VNP$.

2. Generalize the statement of part (1) to hold if instead we have $\Phi$ being any boolean formula of polynomial size.

3. Use part (2) to conclude that the permanent polynomial $Per \in VNP$.

Problem 3 - Some families in VP (20 points)

Part 1 (10 points)

Consider the elementary symmetric polynomial of degree $d$ in $n$ variables.

$$ ES_d(x_1, \ldots, x_n) = \sum_{\substack{S \subset [n] \ |S| = d}} \prod_{i \in S} x_i $$

1. Prove that for any pair $(n,d)$ where $n \geq d$ the elementary symmetric polynomial can be computed by a circuit of size $poly(n,d)$ and depth $3$. That is, the elementary symmetric polynomials can also be computed really fast in the parallel model.

Hint: Consider the polynomial $\displaystyle p(x_1, \ldots, x_n, t) = \prod_{i=1}^n (t + x_i)$

Part 2 (10 points)

The Schur polynomials are an important family of polynomials in algebraic combinatorics and representation theory. These polynomials generalize the elementary symmetric polynomials as well as the complete homogeneous symmetric polynomials.

They are defined as follows: given a partition $\lambda := (\lambda_1, \lambda_2, \ldots, \lambda_n)$ where $\lambda_1 \geq \cdots \geq \lambda_n \geq 0$, we have $$ s_\lambda(x_1, \dots, x_n) := \sum_{T \in ST(\lambda)} \prod_{i=1}^n x_i^{t_i} $$ where $ST(\lambda)$ is the set of all semi-standard Young Tableaux of shape $\lambda$ and $t_i$ counts the number of occurrences of the element $i$ in the tableau $T$.

Prove that for any partition $\lambda$ of $d$ into $n$ parts, $s_\lambda$ can be computed by a circuit of size $\mathrm{poly}(n, d)$.

Hint: you do not need to know anything about tableaux to solve this problem! You may want to look up this wikipedia page for an alternative way to write these polynomials and use division elimination.

Problem 4 - Homogenization via Interpolation (20 points)

In lecture we saw how to efficiently compute the homogeneous component of a circuit of any degree, by transforming the circuit. Here we will new see how to efficiently compute the homogeneous component of a circuit via interpolation.

Let $\Phi(x_1, \ldots, x_n)$ be a circuit of size $s$ computing a polynomial $f(x_1, \ldots, x_n)$ of degree $d$. Let $$f(x_1, \ldots, x_n) = \sum_{i=0}^d f_i(x_1, \ldots, x_n)$$ be the decomposition of $f$ into its homogeneous components.

Let $t$ be a new formal variable and consider the polynomial $f(tx_1, \ldots, tx_n)$ computed by $\Phi(tx_1, \dots, t x_n)$.

Use interpolation to extract the degree $k$ homogeneous component of $f$ from the polynomial computed by $\Phi(tx_1, \dots, t x_n)$.

Problem 5 - Matrix Multiplication and Circuit Complexity (20 points)

Let $X, Y$ be two $n \times n$ matrices. We say that a circuit $\Phi$ computes the product of $X$ and $Y$ if $\Phi$ contains $n^2$ gates $g_{ij}$ such that $g_{ij}$ computes the dot product of the $i$-th row of $X$ and the $j$-th column of $Y$. As we have discussed in class, such circuits capture all algebraic ways to compute the product of two matrices.

Let $\omega$ be the exponent of matrix multiplication, where $\omega$ is defined as follows:

$$ \omega := \inf_{\alpha \in \mathbb{R}} { \exists \ O(n^\alpha) \text{ size algebraic circuit computing } XY }. $$

Let $X = (x_{ij})$, $Y = (y_{ij})$ and $Z = (z_{ij})$ be three symbolic $n \times n$ matrices.

Let $$ P(X, Y, Z) := \sum_{i,j=1}^n z_{ij} \sum_{k=1}^n x_{ik} y_{kj}. $$ Note that the coefficient of $z_{ij}$ in $P$ is the dot product of the $i$-th row of $X$ and the $j$-th column of $Y$. That is, it computes the $i,j$-th entry of the product of $X$ and $Y$.

1. Let $\Phi$ be a circuit of size $s$ computing $P$. Show that $\omega \leq \log_n(s)$.

2. Let $\Psi$ be a circuit of size $s := n^\alpha$ computing the product of $X$ and $Y$. Show that $\Psi$ can be transformed into a circuit of size $O(s)$ computing $P$.

Thus, we have reduced the problem of computing the exponent of matrix multiplication to the problem of computing the size of a circuit computing a specific polynomial.