
\documentclass[10pt]{article}
\usepackage{amsmath, amssymb, amsthm, amsfonts, bbm}
\usepackage{enumerate}
\usepackage{fullpage}

\DeclareMathOperator*{\argmin}{argmin}
%\usepackage{epsfig}

\begin{document}
\input{preamble.tex}
\newcommand{\bbQ}{\mathbb{Q}}
\newcommand{\bbZ}{\mathbb{Z}}
\renewcommand{\mod}{\mathrm{mod}\ }
\newcommand{\coeffs}{\mathrm{coeffs}}
\newcommand{\Res}{\mathrm{Res}}

\newcommand{\inbrace}[1]{\left \{ #1 \right \}}
\newcommand{\inparen}[1]{\left ( #1 \right )}
\newcommand{\insquare}[1]{\left [ #1 \right ]}
\newcommand{\inangle}[1]{\left \langle #1 \right \rangle}
\newcommand{\infork}[1]{\left \{ \begin{matrix} #1 \end{matrix} \right .}
\newcommand{\inmat}[1]{\begin{matrix} #1 \end{matrix}}
\newcommand{\inbmat}[1]{\begin{bmatrix} #1 \end{bmatrix}}
\newcommand{\insqmat}[1]{\insquare{\begin{matrix} #1 \end{matrix}}}
\newcommand{\inabs}[1]{\begin{vmatrix} #1 \end{vmatrix}}

\newtheorem{problem}{Problem}

\lecture{15}{April 1, 2015}{Madhu Sudan}{Tianren Liu}

%%%% body goes in here %%%%
\paragraph{Today's Topic}
\begin{itemize}
  \item Homogenization
  \item Division Removal
  \item Partial Derivatives
  \item Width Reduction
  \item Depth Reduction
  \item Determinant
\end{itemize}

\paragraph{Homogenization} (Low intermediate degree)
%
Consider arithmetic circuits on field $\mathbb F$ with operations $\{+,\cdot\}$. 
%
If we need an arithmetic circuit computing a low degree polynomial,
% Given a circuit computing a low degree polynomial,
%If the degree of 
does it helps to have intermediate computations of high degree?

\begin{theorem}\label{thm:lowmeddeg}
  If an arithmetic circuit $C$ compute a polynomial $f$ that,
  $\deg(f) \leq d$, $\operatorname{size}(C) \leq s$, 
%
  then there exists a circuit $C'$ computing $f$
  that all intermediate polynomial of $C'$ is of degree $\leq d$,
  and $\operatorname{size}(C') = O(s\cdot d)$, 
  $\operatorname{depth}(C') = O(\log s)\cdot \operatorname{depth}(C)$.
\end{theorem}
To prove this theorem, we introduce definition of homogeneous $i$-th degree component of a polynomial.
Define $\operatorname{Hom}_i(f) = \text{homogeneous $i$-th degree part of $f$}$.
Formally, for polynomial 
$f = \sum_{\vec e} c_{\vec e} x^{\vec e}$,
define
\[
  % f = \sum_{\vec e} c_{\vec e} x^{\vec e} 
  % \implies
  \operatorname{Hom}_i(f) = \sum_{\vec e:\sum_j e_j = i} c_{\vec e} x^{\vec e}.
\]
The Theorem \ref{thm:lowmeddeg} follows from the following lemma as $f = \sum_{i\leq d} \operatorname{Hom}_i(f)$.

\begin{lemma}[Homogenization Lemma]
  If $f$ has circuit $C$ of size $s$,
  then $\{\operatorname{Hom}_i(f)\}_{i\leq d}$ can be computed by
  a circuit of size $O(s\cdot d)$, depth $O(\operatorname{depth}(C) \cdot \log s)$.
\end{lemma}

\begin{proof}
  The new circuit will compute the homogeneous $i$-th degree component of each intermediate polynomial in $C$ ($i\leq d$).
  By simple induction,
  if $f = f_1 + f_2$,
  \[
    \operatorname{Hom}_i(f) = \operatorname{Hom}_i(f_1)  + \operatorname{Hom}_i(f_2) 
    ,
  \]
  % then $\operatorname{Hom}_i(f) $
  if $f = f_1 \cdot f_2$,
  \[
    \operatorname{Hom}_i(f) = \sum_{j\leq i} \operatorname{Hom}_j(f_1) \cdot \operatorname{Hom}_{i-j}(f_2) 
    .
  \]
  So for each intermediate polynomial, 
  given the homogeneous components of lower layers, 
  its homogeneous components can be computed in $O(d)$ space and $O(\log s)$ extra depth.
\end{proof}


\paragraph{Division Removal}
%
Division gates is not necessary for an arithmetic circuit. 
If an arithmetic circuit computing a low degree polynomial with division gates,
then we could remove the divsision without blowing up size or depth. 

\begin{lemma}
  If $f \in \mathbb F[x_1,\ldots,x_n]$ cna be computed by
  a depth $\Delta$, size $s$ circuit over $\{+,\cdot,\div\}$ and $\deg (f) =d$.
%
  Then $f$ can be computed by a circuit of depth $O(\log s)\cdot \Delta$ and size $\poly(s,d)$ over $\{+,\cdot\}$.
\end{lemma}

\begin{proof}
% \begin{itemize}
%   \item Intermediate computation = rational functions
%   \item for $O(1)$ loss in size and depth, can maintain numeratoo (fenzi) \& clenominator (fenmu) seperately
%   \item $f = \frac{g}{h}$
% \end{itemize}
Notice that
each intermediate computation is a rational function $f_i = g_i/h_i$. 
%
Which $O(1)$ loss in size and depth, 
we can compute the numerator and denominator of each node seperately.
\begin{align*}
  f = f_1 + f_2 &\implies \frac{g}{h} = \frac{g_1}{h_1} + \frac{g_2}{h_2} = \frac{g_1h_2 + g_2h_1}{h_1h_2},
\\
  f = f_1 \cdot f_2 & \implies  \frac{g}{h} = \frac{g_1}{h_1}  \frac{g_2}{h_2} = \frac{g_1g_2}{h_1h_2}.
\end{align*}
This would produce an arithmetic circuit computing $g,h$ over $\{+,\cdot\}$.
such that $f = \frac{g}{h}$

Assume w.l.o.g.\ $h(0) = 1$
\[
  f = \frac{g}{h}
  = \frac{g}{1-(1-h)}
  = \sum_{i\geq 0} g(1-h)^i
\]
\[
  \operatorname{Hom}_j(f) 
  = \operatorname{Hom}_j\biggl( \sum_{i\geq 0} g(1-h)^i \biggr)
  = \operatorname{Hom}_j\biggl( \sum_{i\geq 0}^j g(1-h)^i \biggr)
\]
By Homogenization Lemma,
the homogeneous components of $g,h$
can be computed by a depth $O(\log s)\cdot \Delta$ size $\poly(s,d)$ circuit over $\{+,\cdot\}$.
\end{proof}

\paragraph{Partial Derivatives} [Baur Strassen]
\begin{theorem}
Given circuit computing $f(x_1,\ldots,x_n) \in \mathbb F[x_1,\ldots,x_n]$ of size $s$.
There exists circuit of size $O(s)$ computing 
\[
  \biggl( \frac{\partial f}{\partial x_1}, \ldots, \frac{\partial f}{\partial x_n} \biggr).
\]
\end{theorem}

% (Form last lecutre,) (as a cor)
As a corollary
if computing $\phi: \mathbb F^n \to \mathbb F^m$ need size $s$,
then 
\[
  \hat\phi: \mathbb F^n \times \mathbb F^m \to \mathbb F \qquad
  \hat\phi(\vec x,\vec y) = \sum y_i \phi(\vec x)
\]
needs a $\Omega(s)$ size circuit to compute. 

\begin{proof}
It's prove by induction. 
Instead of a naive approach computing the partial derivative of each gate wrt to input,
we compute the partial derivative of output wrt to each gate.

A circuit can be formalized as a straight line program,
\[
  \begin{aligned}
  x_1 \\
  \vdots \\
  x_n \\
  y_1 & \gets x_1 + x_2 \\
  \vdots \\
  y_s & \gets y_{s-1} \cdot y_{s-2}
  \end{aligned}
\]
A circuit can also be viewed a series of substitutions. 
\begin{align*}
  \Psi_s(x_1,\ldots,x_n, y_1,\ldots,y_s) &= y_s \\
  \Psi_s(x_1,\ldots,x_n, y_1,\ldots,y_{s-1}) &= \Psi_s |_{y_s \gets y_{s-1} \cdot y_{s-2}} \\
  \vdots &\\
  \Psi_0(x_1,\ldots,x_n) &= \Psi_1 |_{y_1 \gets x_1+x_2} \\
\end{align*}

Use induction, $\Psi_s$ is the base case,
in which the partial derivatives of $\Psi_s$ can be trivially computed in $O(1)$ size
\[
  \frac{\partial \Psi_s}{\partial x_j} = 0 \qquad
  \frac{\partial \Psi_s}{\partial y_j} = \delta_{js}
\]
% $\frac{\partial \Psi_s}{\partial x_i} = \frac{\partial \Psi_s}{\partial y_j} = 0$ for $j\neq s$. 

Assume for some index $i$, we have a circuit computing
\[
  \frac{\partial \Psi_i}{\partial x_j}, \frac{\partial \Psi_i}{\partial y_j}.
\]
Let $y_i \gets y_l + y_k$ or $y_i \gets y_l \cdot y_k$, we want to compute
\[
  \frac{\partial \Psi_{i-1}}{\partial x_j}, \frac{\partial \Psi_{i-1}}{\partial y_j}
\]

As $\Psi_{i-1}(\ldots,y_{i-1}) = \Psi_{i}(\ldots,y_{i-1}, y_i(y_l,y_k))$,
the partial derivatives of $\{x_j\},\{y_j\}$ besides $y_l,y_k$ are the same
\begin{align*}
  \frac{\partial \Psi_{i-1}}{\partial x_j}(x_1,\ldots,x_n, y_1,\ldots,y_{i-1})
  &= \frac{\partial \Psi_{i}}{\partial x_j}(x_1,\ldots,x_n, y_1,\ldots,y_{i-1},y_i(y_l,y_k))
\\
  \frac{\partial \Psi_{i-1}}{\partial y_j}(x_1,\ldots,x_n, y_1,\ldots,y_{i-1})
  &= \frac{\partial \Psi_{i}}{\partial y_j}(x_1,\ldots,x_n, y_1,\ldots,y_{i-1},y_i(y_l,y_k)) \qquad j\notin\{l,k\}
\end{align*}
for $y_l,y_k$
\[
\begin{aligned}
 & \frac{\partial \Psi_{i-1}}{\partial y_l}(x_1,\ldots,x_n, y_1,\ldots,y_{i-1}) \\
 ={}& \frac{\partial \Psi_{i}}{\partial y_l}(x_1,\ldots,x_n, y_1,\ldots,y_{i-1},y_i(y_l,y_k))
  + \frac{\partial \Psi_{i}}{\partial y_i}(x_1,\ldots,x_n, y_1,\ldots,y_{i-1},y_i(y_l,y_k)) 
  \frac{\partial y_i(y_l,y_k)}{\partial y_l}
  .
\end{aligned}
\]
If $y_i \gets y_l + y_k$, $\frac{\partial y_i(y_l,y_k)}{\partial y_l} = 1$;
if $y_i \gets y_l \cdot y_k$, $\frac{\partial y_i(y_l,y_k)}{\partial y_l} = y_k$.

The circuit computing the derivatives of $\Psi_{i-1}$ has $O(1)$ more gates than the circuit computing derivatives of $\Psi_{i}$. 
Therefore, there exists circuit of size $O(s)$ computing the derivatives of $f = \Psi_0$.
\end{proof}

\paragraph{Width Reduction}

When the memory is limited,
consider a register machine model of computation. 
Memory is a set of registers $M = \{R_1,\ldots,R_m\}$. 
%
Unlikely previous model where all intermediate result is stored and can be later used,
the machine could only remember $m$ intermediate results.
%
The arithmetic computation can be considered as a straight line program
\[
  \begin{aligned}
    R_1 &\gets X_1 + \gamma X_2 \\
    R_2 &\gets \alpha R_1 + \beta X_5 \\
    R_1 &\gets \ldots \\
    \vdots
  \end{aligned}
\]

\begin{theorem}[Barrington]
  If boolean $\phi$ has formula size $s$
  implies $\phi$ can be computed with $\log_2 s$ bits of memory in size $s^2$.
\end{theorem}

\begin{theorem}[Ben-Or-Clere]
  If polynomial $f$ has formula size $s$,
  then $f$ can be computed by 3-register machine in size $s^2$.
\end{theorem}

\begin{proof}
  If $f \gets f_1 \cdot f_2$,
  then $\operatorname{size}(f) = \operatorname{size}(f_1) + \operatorname{size}(f_2)$. 
  First we should applies ... to balance the formula,
  so that the formula, viewed as a binary tree, is balanced. 
  This would introduce an $O(1)$-factor on the size (NEED VERIFY). 

  In Ben-Or-Clere, 
  we are looking for a computation sequence that 
  \[
    % \begin{aligned} \boxed{R_1} &\to \\ \boxed{R_2} &\to \\ \boxed{R_3} &\to \end{aligned} 
    \begin{aligned} R_1 \\ R_2 \\ R_3 \end{aligned} 
    \begin{gathered} \to \\ \to \\ \to \end{gathered} 
    \boxed{\begin{aligned}~\\\quad f\quad \\~\end{aligned}}
    \begin{gathered} \to \\ \to \\ \to \end{gathered} 
    \begin{aligned} &R_1 \\ &R_2 \\ &R_3 + f(x_1,\ldots,x_n) R_2 \end{aligned} 
    % \begin{aligned} &\to \boxed{R_1} \\ &\to \boxed{R_2} \\ &\to \boxed{R_3 + f(x_1,\ldots,x_n) R_2} \end{aligned} 
  \]
  The sequence takes the initial values stored in the registers as a part of the inputs.
  If the registers is initialized as $R_2=1,R_3=0$,
  then such sequence will compute $f(x)$.

  Assuming we've found such computation sequence for $f_1$ and $f_2$,
  to compute $f = f_1+f_2$,
  \[
    \begin{aligned} R_1 \\ R_2 \\ R_3 \end{aligned} 
    \begin{gathered} \to \\ \to \\ \to \end{gathered} 
    \boxed{\begin{aligned}~\\\quad f_1\quad \\~\end{aligned}}
    \begin{gathered} \to \\ \to \\ \to \end{gathered} 
    \begin{aligned} &R_1 \\ &R_2 \\ &R_3 + f_1(x) R_2 \end{aligned} 
    \begin{gathered} \to \\ \to \\ \to \end{gathered} 
    \boxed{\begin{aligned}~\\\quad f_2\quad \\~\end{aligned}}
    \begin{gathered} \to \\ \to \\ \to \end{gathered} 
    \begin{aligned} &R_1 \\ &R_2 \\ &R_3 + f_1(x) R_2 +f_2(x) R_2 \end{aligned},
  \]
  to compute $f = f_1f_2$, 
  \[
    \begin{aligned} R_1 \\ R_2 \\ R_3 \end{aligned} 
    \begin{gathered} \to \\ \to \\ \to \end{gathered} 
    \boxed{\begin{aligned}~\\ f_1 \\~\end{aligned}}
    \begin{gathered} \to \\ \to \\ \to \end{gathered} 
    \begin{aligned} &R_1 \\ &R_2 \\ &R_3 + f_1(x) R_2 \end{aligned} 
    \begin{gathered} \to \\ \to \\ \to \end{gathered} 
    \boxed{\begin{aligned}\vphantom{\vdots}\\ f_2 \\\vphantom{\vdots}\end{aligned}}
    \begin{gathered} \to \\\\ \to \\ \to \end{gathered} 
    \begin{aligned} &R_1 + f_2(x) R_3 \\&+ f_1(x)f_2(x) R_2 \\ &R_2 \\ &R_3 + f_1(x) R_2 \end{aligned}
    \begin{gathered} \to \\\\ \to \\ \to \end{gathered} 
    \boxed{\begin{aligned}\vphantom{\vdots}\\ -f_1 \\\vphantom{\vdots}\end{aligned}}
    \begin{gathered} \to \\\\ \to \\ \to \end{gathered} 
    \begin{aligned} &R_1 + f_2(x) R_3 \\&+ f_1(x)f_2(x) R_2 \\ &R_2 \\ &R_3 \end{aligned}
    \begin{gathered} \to \\\\ \to \\ \to \end{gathered} 
    \boxed{\begin{aligned}\vphantom{\vdots}\\ -f_2 \\\vphantom{\vdots}\end{aligned}}
    \begin{gathered} \to \\\\ \to \\ \to \end{gathered} 
    \begin{aligned} &R_1 \\&+ f_1(x)f_2(x) R_2 \\ &R_2 \\ &R_3 \end{aligned}
  \]

  In either case, 
  $\operatorname{size}_\textrm{3-Reg}(f) 
  \leq 2 \operatorname{size}_\textrm{3-Reg}(f_1) + 2 \operatorname{size}_\textrm{3-Reg}(f_2)$.
\end{proof}


\paragraph{Depth Reduction}

(If we have a depth reduction method,)
consider boolean circuit
and operations $\{+,\cdot\}$ (which is complete). 
Then we would have a general method to reduce depth of boolean circuit. 
(Which is unlikely.)

\begin{theorem}
  $f$ computed by size $s$ circuit, $\deg(f) = d$
  $\implies$ $f$ can be computed in size $\poly(s,d)$ depth $(\log s) (\log d)$
\end{theorem}

\newcommand{\Ppoly}{P/_{\mathrm{poly}}}
\newcommand{\comp}{\mathcal{C}}

\textbf{Remark:} Then $s = \poly(n)$,
size $s$ boolean circuit is $\Ppoly$ class,
size $\poly(s,d)$ depth $(\log s) (\log d)$ boolean circuit is like $\comp{NC}_2$ class.
The reason why we didn't prove $\Ppoly \subseteq \comp{NC}_2$ is when we transfer a boolean circuit to a boolean formula,
the degree of output may blow up.

\begin{proof}
  Let $f_v(x_1,\ldots,x_n)$ be function computed by gate $v$,
  $\partial_{v,w}(x_1,\ldots,x_n)$ be partial derivative of gate $v$ wrt gate $w$.

  Set $w$ as a variable, gives $\tilde f_v(x_1,\ldots,x_n,w)$,
  then
  \[
    \partial_{v,w}(x_1,\ldots,x_n) 
    = \frac{\partial \tilde f_v}{\partial w} (x_1,\ldots,x_n,f_w)
  \]

  In $i$-th stage, compute 
  \begin{itemize}
    \item all $f_w$ that $\deg(f_w) \in \{2^i,\ldots,2^{i+1}-1\}$ 
    \item all $\partial_{v,w}$ that $\deg(\partial_{v,w}) \in \{2^i,\ldots,2^{i+1}-1\}$ 
  \end{itemize}
  (from previous stage) in $\log s$ depth. 
\end{proof}



\end{document}
