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
Related Tags
arithmetic-circuits × 87circuit-complexity × 38
cc.complexity-theory × 37
algebraic-complexity × 20
lower-bounds × 10
reference-request × 6
boolean-functions × 6
determinant × 6
ds.algorithms × 5
circuits × 5
polynomials × 4
permanent × 4
circuit-depth × 4
lo.logic × 2
optimization × 2
big-picture × 2
matrices × 2
derandomization × 2
p-vs-np × 2
gr.group-theory × 2
matrix-product × 2
circuit-families × 2
monotone × 2
formulas × 2
cc-complexity-theory × 2