**Problem Detail:**

I was reading the proof that for every arithmetic circuit of size $s$ and depth $d$ we can find a circuit $D$ of size $\mathcal{O}(s)$ and depth $\mathcal{O}(d)$. I do not understand what is meant when we say that we can construct a circuit which 'simultaneously computes' all partial derivatives of a function. Does simultaneously computing mean that there are multiple output gates or does it mean that every partial derivative is computed by some sub-circuit of of $D$.

###### Asked By : user13987

###### Answered By : Yuval Filmus

The new circuit will have multiple output gates, each one computing a different partial derivative. See for example Definition 2.1 and the ensuing proof in lecture notes of Wigderson.

Question Source : http://cs.stackexchange.com/questions/53417

**3200 people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback