Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates
Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates
复制标题
具有任意门的深度 2 和深度 3 布尔电路的下界
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
D. Cherukhin
中科院分区：
文献类型：
--
作者：
D. Cherukhin
我们考虑深度2和3电路的基础上组成的所有布尔函数。对于深度为3的电路，我们证明了计算循环卷积的任何电路的大小的下界Ω（n log n）。对于深度为2的电路，在我们以前的论文[10]中得到了相同函数的下界Ω（n3/2）。在这里，我们提出了一个改进的证明这个界限。这两个下界分别是深度3和深度2电路的最佳已知下界。
We consider depth-2 and 3 circuits over the basis consisting of all Boolean functions. For depth-3 circuits, we prove a lower bound Ω(n log n) for the size of any circuit computing the cyclic convolution. For depth-2 circuits, a lower bound Ω(n3/2) for the same function was obtained in our previous paper [10]. Here we present an improved proof of this bound. Both lower bounds are the best known for depth-3 and depth-2 circuits, respectively.