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.

  • 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$ Nov 1 at 17:05
  • $\begingroup$ (When you duplicate a gate, you duplicate the entire sub-circuit that feeds into that gate as well.) $\endgroup$ Nov 1 at 17:42


Your Answer

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