0
$\begingroup$

I was reading Ramprasad Saptharishi's survey on Arithmetic Circuits. There in section 2.1.1 fact 2.3 it has

Any arithmetic circuit of of depth $\Delta$ and size $s$, can be simulated by an arithmetic formula of depth $\Delta$ and size $s'\leq s^{\Delta}$

I tried to do this. But i am getting $s^s$ how $s^{\Delta}$ because from node it can go to at most $s-1$ nodes or gates. So $s^s$.

It is written obviously. But i am failing to find to so. How this result is coming.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Start from the inputs, induct on depth. If a gate has fan-out more than one, duplicate that gate a number of times equal to its fanout. It's fan-out is at most $s$. So each time you duplicate a layer of gates, you multiply the size by at most $s$. This happens at most depth many times. $\endgroup$
    – Joshua Grochow
    Nov 1, 2022 at 17:05
  • $\begingroup$ (When you duplicate a gate, you duplicate the entire sub-circuit that feeds into that gate as well.) $\endgroup$
    – Joshua Grochow
    Nov 1, 2022 at 17:42

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.