Lower Bounds for Depth-Three Arithmetic Circuits with small bottom fanin
Lower Bounds for Depth-Three Arithmetic Circuits with small bottom fanin
复制标题
具有小底部扇形的深度三算术电路的下界
DOI：
--
复制
发表时间：
2015
影响因子：
1.4
通讯作者：
Chandan Saha
中科院分区：
文献类型：
--
作者：
N. Kayal;Chandan Saha
Shpilka＆Wigderson（IEEE计算复杂性会议，第87卷，1999年）提出了一个问题，即证明（非均匀的）深度三个算术回路（无均匀）的下限，带有有限的底部fanin在field上，{Mathbb {f}}} {f}}}特征零的$$ F。底部fanin最多最多$$ {au} $$τ计算一个显式$$ {n} $$ n-n-variate tem $$ $$ {d} $$ d of $ $ d of $ $ {{mathbb {f}}} $$ f。同时，Nisan＆Wigderson（Comp Complex 6（3）：217–234，1997）提出了证明均质深度五个算术回路的超级多项式下限的问题。 $$ {n^{omega（sqrt {d}）} $$nΩ（d）均匀的深度五电路（也用于深度为三个电路），最多可用于$$ {n^{mu}} $$Nμ解决了Nisan和Wigderson提出的问题仅部分是因为对底部的Fanin的额外限制（一般的同质深度五电路最多具有底部的Fanin $$ {N} $$ n）。
Shpilka & Wigderson (IEEE conference on computational complexity, vol 87, 1999) had posed the problem of proving exponential lower bounds for (nonhomogeneous) depth-three arithmetic circuits with bounded bottom fanin over a field $${{mathbb{F}}}$$F of characteristic zero. We resolve this problem by proving a $${N^{Omega(frac{d}{ au})}}$$NΩ(dτ) lower bound for (nonhomogeneous) depth-three arithmetic circuits with bottom fanin at most $${ au}$$τ computing an explicit $${N}$$N-variate polynomial of degree $${d}$$d over $${{mathbb{F}}}$$F. Meanwhile, Nisan & Wigderson (Comp Complex 6(3):217–234, 1997) had posed the problem of proving super-polynomial lower bounds for homogeneous depth-five arithmetic circuits. Over fields of characteristic zero, we show a lower bound of $${N^{Omega(sqrt{d})}}$$NΩ(d) for homogeneous depth-five circuits (resp. also for depth-three circuits) with bottom fanin at most $${N^{mu}}$$Nμ, for any fixed$${mu < 1}$$μ<1. This resolves the problem posed by Nisan and Wigderson only partially because of the added restriction on the bottom fanin (a general homogeneous depth-five circuit has bottom fanin at most $${N}$$N).