<p>See that <span class="math-container">$w\in \mathcal{F}_m$</span> so <span class="math-container">$\deg(w)\geq m$</span> but <span class="math-container">$\deg(w_L),\deg(w_R)&lt;m$</span>. So if <span class="math-container">$\deg(w_L)=\deg(w_R)=m-1$</span> then <span class="math-container">$\deg(w)$</span> becomes <span class="math-container">$2m-2$</span>. If <span class="math-container">$m$</span> is large enough then <span class="math-container">$2m-2 &gt;m$</span>. Hence we can certainly have <span class="math-container">$\deg(w)&gt;m$</span>. Then <span class="math-container">$\deg([w])&gt;m$</span> and all the terms in RHS  will not have degree at most <span class="math-container">$\deg(u)/2$</span></p>
<p>Similarly think about the second part.</p>

CC BY-SA 4.0
2023-03-21T00:04:11.370Z
2023-03-21T00:04:11.370Z
Sassy Math
<p>In the  <a href="https://github.com/dasarpmar/lowerbounds-survey/releases/download/v9.0.3/fancymain.pdf" rel="nofollow noreferrer">survey</a> see section 5.3.2 : Depth reduction for arithmetic circuits for notations.</p>
<p>I follow the proof of the following two identities :</p>
<p><span class="math-container">$[u]=\Sigma_{w\in \cal{F}_m}[u:w].[w]$</span>  where <span class="math-container">$deg(u)\geq m$</span>  and</p>
<p><span class="math-container">$[u:v]=\Sigma_{w \in \cal{F}_m} [u:w][w:v]$</span> where <span class="math-container">$deg(u)\geq m \gt deg(v)$</span></p>
<p>By using these identities we are trying to reduce the depth of the circuit.</p>
<p>The idea it to write <span class="math-container">$[u]$</span> as product of polynomials that have degree at most half the degree of <span class="math-container">$[u]$</span>.</p>
<p>Let <span class="math-container">$\cal{F}(u)=\cal{F}_m$</span> where <span class="math-container">$m=deg(u)/2$</span>  and</p>
<p><span class="math-container">$\cal{F}(u,v)=\cal{F}_m$</span> where <span class="math-container">$m=(deg(u)+deg(v))/2$</span> .</p>
<p>Then we have</p>
<ol>
<li><p><span class="math-container">$[u]=\Sigma_{w\in \cal{F}(u)}[u:w].[w]$</span> and</p>
</li>
<li><p><span class="math-container">$[u:v]=\Sigma_{w \in \cal{F}(u,v)} [u:w][w:v]$</span>.</p>
</li>
</ol>
<p>The proof in the survey further expands both the equations writing <span class="math-container">$[w]$</span> as <span class="math-container">$[w_L].[w_R]$</span> in the first equation and <span class="math-container">$[w:v]$</span> as <span class="math-container">$[w_L].[w_R:v]$</span> in the second.</p>
<p>However I see no need for this as for the 1st equation we have</p>
<p>degree on RHS = <span class="math-container">$deg(u)$</span></p>
<p>degree on LHS : degree of <span class="math-container">$[u:w] \leq deg(u)-deg(w)$</span> and degree of <span class="math-container">$[w] = m = deg(u)/2$</span> as <span class="math-container">$w\in \cal{F}(u)$</span> .</p>
<p>For the second equation :</p>
<p>degree on RHS = <span class="math-container">$deg(u) - deg(v)$</span></p>
<p>degree on LHS <span class="math-container">$deg[u:w] \leq deg(u) -deg(w) = (deg(u)-deg(v))/2$</span> and <span class="math-container">$deg[w:v] \leq (deg(u)-deg(v))/2$</span> as <span class="math-container">$deg(w) = (deg(u)+deg(v))/2$</span>  for all <span class="math-container">$w's$</span>.</p>
<p>So my question is why in the proof presented in the survey, they are expanding further. They claim that the degrees are not yet halved if do not expand further but my working above shows that the degrees are halved.</p>
<p>Have I misunderstood anything here ?</p>

<circuit-complexity><arithmetic-circuits><circuit-depth>
doubt in the proof of reducing any arithmetic circuit to log(d) depth, where d is the degree of the polynomial it is computing
emmy
# doubt in the proof of reducing any arithmetic circuit to log(d) depth, where d is the degree of the polynomial it is computing

(Asked by: username_0 on 2023-03-19)

In the [survey](https://github.com/dasarpmar/lowerbounds-survey/releases/download/v9.0.3/fancymain.pdf) see section 5.3.2 : Depth reduction for arithmetic circuits for notations.

I follow the proof of the following two identities :

$[u]=\Sigma\_{w\in \cal{F}\_m}[u:w].[w]$ where $deg(u)\geq m$ and

$[u:v]=\Sigma\_{w \in \cal{F}\_m} [u:w][w:v]$ where $deg(u)\geq m \gt deg(v)$

By using these identities we are trying to reduce the depth of the circuit.

The idea it to write $[u]$ as product of polynomials that have degree at most half the degree of $[u]$.

Let $\cal{F}(u)=\cal{F}\_m$ where $m=deg(u)/2$ and

$\cal{F}(u,v)=\cal{F}\_m$ where $m=(deg(u)+deg(v))/2$ .

Then we have

1. $[u]=\Sigma\_{w\in \cal{F}(u)}[u:w].[w]$ and
2. $[u:v]=\Sigma\_{w \in \cal{F}(u,v)} [u:w][w:v]$.

The proof in the survey further expands both the equations writing $[w]$ as $[w\_L].[w\_R]$ in the first equation and $[w:v]$ as $[w\_L].[w\_R:v]$ in the second.

However I see no need for this as for the 1st equation we have

degree on RHS = $deg(u)$

degree on LHS : degree of $[u:w] \leq deg(u)-deg(w)$ and degree of $[w] = m = deg(u)/2$ as $w\in \cal{F}(u)$ .

For the second equation :

degree on RHS = $deg(u) - deg(v)$

degree on LHS $deg[u:w] \leq deg(u) -deg(w) = (deg(u)-deg(v))/2$ and $deg[w:v] \leq (deg(u)-deg(v))/2$ as $deg(w) = (deg(u)+deg(v))/2$ for all $w's$.

So my question is why in the proof presented in the survey, they are expanding further. They claim that the degrees are not yet halved if do not expand further but my working above shows that the degrees are halved.

Have I misunderstood anything here ?

**Tags:** circuit-complexity, arithmetic-circuits, circuit-depth

---

## 1 answers

### Answer by username_1 on 2023-03-21. Score: 1 | Accepted answer

See that $w\in \mathcal{F}\_m$ so $\deg(w)\geq m$ but $\deg(w\_L),\deg(w\_R). So if $\deg(w\_L)=\deg(w\_R)=m-1$ then $\deg(w)$ becomes $2m-2$. If $m$ is large enough then $2m-2 >m$. Hence we can certainly have $\deg(w)>m$. Then $\deg([w])>m$ and all the terms in RHS will not have degree at most $\deg(u)/2$

Similarly think about the second part.


---

