New answers tagged arithmetic-circuits
0
votes
doubt in the proof of reducing any arithmetic circuit to log(d) depth, where d is the degree of the polynomial it is computing
See that $w\in \mathcal{F}_m$ so $\deg(w)\geq m$ but $\deg(w_L),\deg(w_R)<m$. 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 ...
- 203
Top 50 recent answers are included