1
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ Several output gates. This is also apparent from the proof. $\endgroup$ – Yuval Filmus Feb 21 '16 at 6:46
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.