\documentclass[english,onecolumn,problemset,oneside]{notes}
\input{thmmacros}
\usetikzlibrary{decorations.pathreplacing,arrows}
\title{Algebraic Circuit Complexity}
\problemset{3 %Solutions
}
% \author{Arthur Vandaley}
\duedate{12}{11}{2017}
\begin{document}
\noindent\hfil\rule{0.5\textwidth}{.4pt}\hfil
\newcommand{\Det}{\operatorname{Det}}
\newcommand{\Perm}{\operatorname{Perm}}
\newcommand{\IMM}{\operatorname{IMM}}
\newcommand{\Tr}{\operatorname{Tr}}
\section*{Instructions}
\begin{itemize}
\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 12th November 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{itemize}
\noindent\hfil\rule{0.5\textwidth}{.4pt}\hfil
\section*{Questions}
\begin{psquestion} {\rm \textbf{(10 points)}}
Let $f(\vecx) \in \Q[\vecx]$ is an $n$-variate degree $d$ polynomial. Suppose you are told that $\dim \set{\partial^{=*}(f)} \leq r$ (the dimension of partial derivatives of \emph{all} orders). Prove that for any partition $\vecx = \vecy \sqcup \vecz$, the partial derivative matrix with respect to this partition has rank at most $\poly(n,d,r)$.
What can you say about the converse?
\end{psquestion}
\vspace{1em}
\begin{psquestion} {\rm \textbf{(10 points)}}
Suppose you are given two sparse $n$-variate polynomials $f(\vecx)$ and $g(\vecx)$ and you are promised the individual degree of $f$ and $g$ with respect to each variable is at most $42$. Construct a \emph{deterministic} polynomial time algorithm to check if $f$ and $g$ have a non-trivial gcd.
\end{psquestion}
\vspace{1em}
\begin{psquestion} {\rm \textbf{(10 points)}}
Say we have an \emph{algebraic formula} (possibly non-homogeneous) of size $s$ computing a homogeneous $n$-variate degree $d$ polynomial $f(\vecx)$. Show that $f(\vecx)$ can also be computed by a \emph{homogeneous algebraic formula} of size at most
\[
\poly\inparen{s,\binom{d + \log s}{d}}.
\]
\aside{Prior to this result, it was conjectured that $\operatorname{ESYM}_d$ cannot have polynomial-sized homogeneous formulas for any non-constant $d$.}
Conclude that the polynomial $\operatorname{ESYM}_d(\vecx)$ for $d = O(\log n)$ has a polynomial-sized \emph{homogeneous algebraic formula} computing it.
\end{psquestion}
\vspace{1em}
\begin{psquestion} {\rm \textbf{(10 points)}}
Suppose you are given a blackbox that computes an $n$-variate degree $\leq d$ polynomial $f(x_1,\ldots, x_n) \in \Q[\vecx]$. You are told that this polynomial has at most $s$ monomials.
Using just $\poly(s,d,n)$ evaluations, reconstruct the polynomial $f(x_1,\ldots, x_n)$ (i.e. figure out each non-zero monomial of $f$ and its coefficient).
\end{psquestion}
\vspace{1em}
\begin{psquestion} {\rm \textbf{(20 points)}}
In class, we looked briefly at Kayal's lower bound for $\Sigma\bigwedge\Sigma\Pi^{[t]}$ circuits computing a monomial $x_1\ldots x_n$. For this, we worked with the dimension of shifted partial derivatives,
\[
\Gamma_{k,\ell}(f) := \dim \set{\vecx^{=\ell}\partial^{=k}(f)}
\]
and proved in class that for any $k,\ell$ we have:
\begin{align*}
\Gamma_{k,\ell}(Q^d) & \leq \binom{n + \ell + (t-1)k}{n} \quad,\quad\text{if $\deg(Q) = t$,}\\
\Gamma_{k,\ell}(x_1^{e_1}\ldots x_n^{e_n}) & \geq \binom{n}{k}\binom{n - k + \ell}{n-k}\quad,\quad\text{if $e_1,\ldots, e_n \geq 1$}.
\end{align*}
\begin{enumerate}
\item {\rm \textbf{(10 points)}} Prove that if $\ell = t n$, there we can choose $k = \epsilon n / t$ for suitably small constant $\epsilon > 0$ such that
\[
\frac{\binom{n}{k}\binom{n-k+\ell}{n-k}}{\binom{n + \ell + (t-1)k}{n}} = 2^{\Omega(n/t)}.
\]
\textcolor{gray}{You might want to use the fact that $(n-b)^{a+b} \leq \frac{(n+a)!}{(n-b)!} \leq (n+a)^{a+b}$ for any $a,b \geq 0$.}
\item {\rm \textbf{(10 points)}} Formally prove that if $0 \neq f = Q_1^d + \cdots + Q_s^d$ with $\deg Q_i = t$ for all $i$, then there must be some non-zero monomial of $f$ of support-size at most $O(t \log s)$.
\end{enumerate}
\end{psquestion}
\begin{psquestion} {\rm \textbf{(40 points)}}
In this problem, we'll extend the previous problem from $\Sigma\bigwedge\Sigma\Pi^{[t]}$ circuits to circuits of the form
\[
C = \sum_{i=1}^s m_i \cdot Q_i^{d}
\]
where each $m_i$ is a monomial, and $\deg(Q_i) = t$. These are also referred to as $\Sigma m \bigwedge \Sigma\Pi^{[t]}$ circuits.
\medskip
For any $i \in [n]$, define the operator $\Delta_i:\F[\vecx] \rightarrow \F[\vecx]$ as $\Delta_i(f) = x_i \cdot \frac{\partial f}{\partial x_i}$. We shall use $\Delta^{=k}$ to refer to the span of $k$-th order operators using these $\Delta_i$'s. That is,
\[
\Delta^{=k}(f) = \operatorname{span}\setdef{\Delta_{i_1} \circ \cdots \circ \Delta_{i_k} (f)}{i_1,\ldots, i_k \in [n]}.
\]
For parameters $k,\ell$, define $\tilde{\Gamma}_{k,\ell}(f) = \dim \set{\vecx^{=(\ell-k)} \Delta^{=k}(f)}$. \aside{The shift degree being $\ell - k$ is just to keep the expressions similar to $\Gamma_{k,\ell}$ in the previous problem, since $\Delta^{=k}$ also accounts for a degree $k$ monomial.}
\begin{enumerate}
\item {\rm \textbf{(15 points)}} Suppose $Q$ is a homogeneous polynomial of degree $t$, and $m$ is an arbitrary monomial. Show that for any $d \geq 0$,
\[
\tilde{\Gamma}_{k,\ell}(m \cdot Q^d) \leq \binom{n + \ell + k(t-1)}{n}.
\]
Also show that if $f = (x_1 + 1)^{e_1}\cdots (x_n+1)^{e_n}$ where $e_1,\ldots, e_n \geq 1$, then
\[
\tilde{\Gamma}_{k,\ell}(f) \geq \binom{n}{k} \binom{n-k+\ell}{n-k}.
\]
\item {\rm \textbf{(5 points)}} Construct an explicit hitting set of size $\poly(n,d,s)^{O(t\log s)}$ for the class of $\Sigma m \bigwedge\Sigma\Pi^{[t]}$ circuits.
\item {\rm \textbf{(20 points)}} Show that the task of checking if a given degree $t$ polynomial $Q(\vecx)$ divides a given sparse polynomial $f(\vecx)$ reduces to PIT of circuits as above.
Formally, suppose you are given a polynomial $f(\vecx)$ that has at most $s$ monomials, and a polynomial $Q(\vecx)$ that has degree at most $t$. Construct a circuit $C$ of the form $\Sigma m \bigwedge \Sigma \Pi^{[t]}$, in polynomial time, such that $C \equiv 0$ if and only if $Q$ divides $f$.
\textcolor{gray}{(Hint: Strassen)}
\end{enumerate}
\end{psquestion}
\vspace{2em}
\noindent\hfil\rule{0.5\textwidth}{.4pt}\hfil
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: "ps3"
%%% End: