\documentclass[english,onecolumn,problemset,oneside]{notes}
\input{thmmacros}
\title{Algebraic Circuit Complexity}
\problemset{1}
\duedate{3}{9}{2017}
\begin{document}
\noindent\hfil\rule{0.5\textwidth}{.4pt}\hfil
\section*{Instructions}
\begin{enumerate}
\item The problem set has {\bf 4 questions} with a total score of {\bf 80 points}.
\item You are expected to work independently.
\item Solutions are expected as a \LaTeX~document. You may similar source files from the Algebra \& Computation course on \href{http://megh.tcs.tifr.res.in/ramprasad/algComp_2017}{megh}.
\item The deadline is 3rd September 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} Assume that $f(x_1,\ldots, x_n)$ is computable by an \emph{algebraic branching program (ABP)} of size $s$.
\begin{enumerate}\itemsep0pt
\item {\bf (10 points)}
Show that $f$ is also computable by an algebraic circuit of \aside{That is, $\text{ABP} \subseteq \text{Circuits}$} size $\poly(s)$.
What is the depth of the circuit that you constructed?
\item {\bf (10 points)} Additionally, if you knew that the ABP \aside{That is (in general), $O(1)\text{-width-ABP} \subseteq \text{Formulas}$.} computing $f$ is a \emph{layered} graph (that is, the nodes are partitioned into disjoint layers and edges go only from layer $i$ to layer $i+1$) with at most $10$ vertices in each layer. Show that $f$ is computable by an \emph{algebraic formula} of size $\poly(s)$.
\end{enumerate}
\end{psquestion}
\vspace{1em}
\begin{psquestion}
We shall say that an ABP is \emph{homogeneous} if
\begin{itemize}\itemsep0pt
\aside{Note that the underlying DAG is, in general, a multi-graph.}
\item the nodes can be partitions into disjoint layers, with edges only going from layer $i$ to layer $i+1$,
\item all edge weights are of the form $\alpha x_i$ for some $\alpha \in \F$.
\end{itemize}
\noindent
{\bf (15 points)} Show that any ABP computing a degree-$d$ homogeneous polynomial $f(x_1,\ldots, x_n)$ can be converted to a \emph{homogeneous ABP} of size $\poly(s,d)$ computing the same polynomial.
\end{psquestion}
\vspace{1em}
\begin{psquestion}
Consider the \emph{complete homogeneous symmetric polynomial} of degree $d$, denoted by $h_d(x_1,\ldots, x_n)$, that is a sum of all monomials of degree $d$ (including non-multilinear monomials) with coefficient $1$ each. For instance,
\[
h_3(x_1,x_2,\ldots, x_n) = \sum_i x_i^3 + \sum_{\substack{1\leq i,j \leq n\\i \neq j}} x_i^2 x_j + \sum_{1\leq i < j < k \leq n} x_i x_j x_k.
\]
\noindent
{\bf (10 points)} For any $d$, show that the polynomial $h_d(x_1,\ldots, x_n)$ is computable by a $\poly(n,d)$-size algebraic circuit over any large enough field.
\end{psquestion}
\vspace{1em}
\begin{psquestion}
Say we are given an algebraic circuit $C(x_1,\ldots, x_n)$ of size $s$ that computes a degree-$d$ polynomial $f(x_1,\ldots, x_n)$.
\begin{enumerate}
\item {\bf (5 points)} Show that the polynomial $\frac{\partial f}{\partial x_1}$ can be computed by an algebraic circuit without much blow-up in size, if $\F$ is large enough.
\item {\bf (5 points)} What can you say if you are instead given a formula for $f$? Can you construct a formula computing $\frac{\partial f}{\partial x_1}$?
\item {\bf (5 points)} What if we have a $\Sigma\Pi\Sigma$ circuit computing $f$? Can you construct a $\Sigma\Pi\Sigma$ circuit computing $\frac{\partial f}{\partial x_1}$ of not-much-larger size?
\item {\bf (5 points)} What about computing $\frac{\partial^i f}{\partial x_1^i}$, for $i = \frac{d}{2}$ say?
\item {\bf (15 points)} Suppose we want to compute the higher-order derivative
\[
g = \frac{\partial^{n/2} f}{\partial x_1\;\partial x_2\; \cdots\; \partial x_{n/2}}.
\]
Given $f$ as a small algebraic circuit, do you think it is possible to compute $g$ by a small algebraic circuit? Try and justify your answer.
\end{enumerate}
\end{psquestion}
\noindent\hfil\rule{0.5\textwidth}{.4pt}\hfil
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: "ps1"
%%% End: