<p>I was reading <a href="https://github.com/dasarpmar/lowerbounds-survey/releases/download/v9.0.3/fancymain.pdf" rel="nofollow noreferrer">Ramprasad Saptharishi's survey on Arithmetic Circuits</a>.
There in section 2.1.1 fact 2.3 it has</p>
<blockquote>
<p>Any arithmetic circuit of of depth <span class="math-container">$\Delta$</span> and size <span class="math-container">$s$</span>, can be
simulated by an arithmetic formula of depth <span class="math-container">$\Delta$</span>  and size <span class="math-container">$s'\leq
 s^{\Delta}$</span></p>
</blockquote>
<p>I tried to do this. But i am getting <span class="math-container">$s^s$</span> how <span class="math-container">$s^{\Delta}$</span> because from node  it can go to at most <span class="math-container">$s-1$</span> nodes or gates. So <span class="math-container">$s^s$</span>.</p>
<p>It is written obviously. But i am failing to find to so. How this result is coming.</p>

CC BY-SA 4.0
2022-11-01T17:05:29.297Z
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.
Joshua Grochow
CC BY-SA 4.0
2022-11-01T17:42:32.890Z
(When you duplicate a gate, you duplicate the entire sub-circuit that feeds into that gate as well.)
Joshua Grochow
<algebraic-complexity><arithmetic-circuits><formulas>
Any arithmetic circuit of size $s$ and depth $\Delta$ can be converted to a formula of size $s' \leq s^{\Delta}$
Sassy Math
# Any arithmetic circuit of size $s$ and depth $\Delta$ can be converted to a formula of size $s' \leq s^{\Delta}$

(Asked by: username_0 on 2022-11-01)

I was reading [Ramprasad Saptharishi's survey on Arithmetic Circuits](https://github.com/dasarpmar/lowerbounds-survey/releases/download/v9.0.3/fancymain.pdf).
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.

**Tags:** algebraic-complexity, arithmetic-circuits, formulas

> **Comments:**
> **username_1**: 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.  
> **username_1**: (When you duplicate a gate, you duplicate the entire sub-circuit that feeds into that gate as well.)  

---

## 0 answers

