\documentclass[english,onecolumn,problemset,oneside]{notes}
\input{thmmacros}
\usetikzlibrary{decorations.pathreplacing,arrows}
\title{Algebraic Circuit Complexity}
\problemset{2 %Solutions
}
% \author{Arthur Vandaley}
\duedate{15}{10}{2017}
\begin{document}
\noindent\hfil\rule{0.5\textwidth}{.4pt}\hfil
\newcommand{\Det}{\operatorname{Det}}
\newcommand{\Perm}{\operatorname{Perm}}
\newcommand{\IMM}{\operatorname{IMM}}
\section*{Instructions}
\begin{enumerate}
\item The problem set has {\bf 6 questions} with a total score of {\bf 100 points}.
\item You are expected to work independently.
\item Solutions are expected as a \LaTeX~document.
\item The deadline is 15th October 2017. You can also submit answers to some (or all) of the questions \textbf{any time after the deadline} (a little before the course ends, of course; they need to be graded) for \textbf{half the credit}.
This is to encourage you to solve all the question in these problem sets, even if it is past the deadline.
\end{enumerate}
\noindent\hfil\rule{0.5\textwidth}{.4pt}\hfil
\section*{Questions}
\begin{psquestion} {\rm \textbf{(10 points)}}
Recall that $\Perm_n$ is the permanent of a symbolic $n\times n$ matrix with distinct variables for each of its entries. If $\F_q$ is the finite field of $q$ elements, then prove that\aside{Even if you can show some non-trivial lower bound for the probability purely as a function of $q$ that would be fine.}
\[
\Pr_{\veca \in_R \F_q^{n^2}}\insquare{\Perm_n(\veca) \neq 0} \geq \frac{q-2}{q-1}.
\]
\textcolor{gray}{(\textbf{Hint:} Koutis + induction)}
\end{psquestion}
\vspace{1em}
\begin{psquestion} {\rm \textbf{(10 points)}}
For a circuit $C$ (with arbitrary fan-ins), we shall say that the \emph{product-depth} of the circuit is $\Delta$ if any path from root to leaf passes through at most $\Delta$ multiplication gates. For instance, a $\Sigma\Pi\Sigma\Pi\Sigma$ circuit has product-depth $2$.
Show that if $f(x_1,\ldots, x_n)$ is a polynomial of degree $d$ that can be computed by an algebraic circuit of size $s$, then for any $\Delta$, it can also be computed by an algebraic circuit of size $s^{O(d^{1/\Delta})}$ and product-depth $\Delta$.
\end{psquestion}
\begin{psquestion} {\rm \textbf{(20 points)}}
Prove a super-polynomial lower bound for $\Sigma\Pi^{[n^{1.5}]}\Sigma$ \aside{Actually, any $n^{2-\delta}$ would also be possible but I just put a specific constant less than $2$.} circuits (that is, depth-$3$ circuits whose formal degree is bounded by $n^{1.5}$) computing $\Det_n$. \\
\noindent
\textcolor{gray}{Recall that $\binom{n}{\alpha n} \approx 2^{H(\alpha) n}$, and $H(\alpha) \approx \alpha \log(1/\alpha)$ when $\alpha$ is small.}
\end{psquestion}
\vspace{1em}
\begin{psquestion} {\rm \textbf{(20 points)}}
Consider circuits of the following kind:
\[
C = \sum_{i=1}^s H_i(\ell_{i,1},\ldots, \ell_{i,r})
\]
\begin{itemize}\itemsep0pt
\item $r = 100$,
\item each $\ell_{i,j}$ is a linear polynomial,
\item each $H_i(z_1,\ldots, z_r) \in \F[z_1,\ldots, z_r]$ \aside{No guarantees on the degree of $H_i$. Could be HUGE, but somehow manages to cancel high-degree terms eventually} is an arbitrary polynomial on $r = 100$ variables.
\end{itemize}
Find an explicit polynomial $f(x_1,\ldots, x_n)$ such that if the above circuit is to compute $f$, then $s$ (the top fan-in) must be exponentially large.
\end{psquestion}
\vspace{1em}
\begin{psquestion} {\rm \textbf{(25 points)}}
Recall the definition of the \emph{iterated matrix multiplication} polynomial $(\IMM_{n,d})$
\[
\IMM_{n,d} = \inparen{ \insquare{\begin{array}{ccc} x_{11}^{(1)} & \cdots & x_{1n}^{(1)}\\ \vdots & \ddots & \vdots \\ x_{n1}^{(1)} & \cdots & x_{nn}^{(1)} \end{array}} \cdots \insquare{\begin{array}{ccc} x_{11}^{(d)} & \cdots & x_{1n}^{(d)}\\ \vdots & \ddots & \vdots \\ x_{n1}^{(d)} & \cdots & x_{nn}^{(d)} \end{array}}}_{1,1}
\]
where each $x_{ij}^{(k)}$ is a distinct variable. \aside{Depends on $(d-2)n^2 + 2n$ variables actually.} This is a homogeneous polynomial of degree $d$ over $\approx n^2d$ variables. For any $0 \leq k \leq d/4$, show that
\[
\dim \inparen{\partial^{=k}(\IMM_{n,d})} \geq n^{k}.
\]
\textcolor{gray}{\textbf{Hint:} Think of $\IMM_{n,d}$ as the canonical width-$n$ ABP where each edge gets a fresh variable as weight. What do derivatives with respect to $k$-edges mean in the ABP computation?
Consider taking derivatives only with respect to layers $2,6,10,14,\ldots, 4k-2$ and set many of the variables in the other layers of $\IMM_{n,d}$ to zero. Do this cleverly so that each such derivative yields a distinct monomial.
}
\end{psquestion}
\vspace{1em}
\begin{psquestion} {\rm \textbf{(15 points)}}
In class, we saw Nisan's partial derivative matrix specifically for multilinear polynomials but it can also be defined for non-multilinear polynomials. For any partition of the variables in to $X = Y \sqcup Z$, define the matrix $M_{Y,Z}(f)$
\begin{tikzpicture}[transform shape, scale=0.9]
\node at (-5,1.5) {$M_{Y,Z}(f) \quad= $};
\draw[fill=black!20] (0,0) rectangle (3,3);
\draw[decorate,decoration={brace,amplitude=10pt,raise=4pt},yshift=0pt]
(0,0) -- (0,3);
\node[anchor=east] at (-0.5,1.5) {Monomials in $Y$};
\draw[decorate,decoration={brace,amplitude=10pt,mirror, raise=4pt},yshift=0pt]
(0,0) -- (3,0);
\node[anchor=north] at (1.5,-0.5) {Monomials in $Z$};
\draw[fill=black!30] (1,0) rectangle (1.5,3);
\node at (1.25,3.2) {$m_Z$};
\draw[fill=black!30] (0,2) rectangle (3,2.5);
\node at (3.5,2.2) {$m_Y$};
\draw[very thick] (1,2) rectangle (1.5,2.5);
\node[anchor=west] at (-3.5,-0.5) {$\mathrm{coeff}_f(m_Y \cdot m_Z)$}
edge[<-,bend right] (1.25,2);
\end{tikzpicture}
The rows and columns would now also involve non-multilinear monomials in $Y$ and $Z$ respectively.\\
If $X = Y \sqcup Z$ is a partition with $|Y| = |Z| = n/2$, what is $\rank(M_{Y,Z}(f))$ for the following polynomials? \aside{You don't need to compute it exactly but you should get a rough estimate (is it $O(1)$, or $\poly(n,d)$ or $\exp(d)$, etc.).}
\begin{enumerate}
\item $f(X) = (x_1 + \cdots + x_n)^d$,
\item $f(X) = \operatorname{ESym}_d$,
\item $f(X) = h_d(x_1,\ldots, x_n)$, \aside{We used the polynomial $h_d$ in the last problem set as well.} the complete homogeneous symmetric polynomial of degree $d$.
\end{enumerate}
\end{psquestion}
\vspace{2em}
\noindent\hfil\rule{0.5\textwidth}{.4pt}\hfil
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: "ps2"
%%% End: