Back to Arithmetic Circuits
Back to notes

# Partial Derivative

0%

Partial derivative is one of the fundamental tools for studying arithmetic circuits.

Let $C$ be an arithmetic circuit computing an $n$-variate polynomial $f$. Denote $X={x_1,\dots,x_n}$. We define the partial derivative of each gate $g$ in $C$ with respect to an input variable $x_i$ inductively as follows.

• If $g$ is an input gate or a constant gate, then define $\partial_{x_i}g=1$ if $g=x_i$; otherwise $\partial_{x_i}g=0$.
• If $g=g_1+g_2$, then define $\partial_{x_i}g=\partial_{x_i}g_1+\partial_{x_i}g_2$.
• If $g=g_1\times g_2$, then define $\partial_{x_i}g=(\partial_{x_i}g_1)\times g_2+g_1\times(\partial_{x_i}g_2)$.

We can further generalize the definition to partial derivative with respect to an internal gate. Let $w$ be an internal gate of $C$, we remove the in-going edges to $w$ and replace it with a variable $y$. We call this new circuit $C_w$. The partial derivative of a gate $g$ in $C$ with respect to $w$ is then naturally defined as the partial derivative of $C_w$ with respect to the new input variable $y$.

To see the nice properties of partial derivative, let us introduce a few more notations. For any gate $v$ in $C$, denote $f_v$ as the function computed by $v$. For any other gate $w$, we denote $f_{v,w}$ as the function computed at $v$ in $C_w$. Finally, the partial derivative of $v$ with respect to $w$ is denoted as $\partial_wf_v$.

• For every gate $v$ and $i\in[n]$, $f_v=(\partial_{x_i}f_v)\cdot x_i + f_{v,x_i}(X,0)$.
• For every pair of gates $v,w$, $f_v=(\partial_w f_v)\cdot f_w+ f_{v,w}(X,0)$.
• For every pair of gates $v,w$, $\partial_wf_v=(\partial_yf_{v,w})|_{y=f_w}$.