Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates

摘要

We consider depth-2 and 3 circuits over the basis consisting of all Boolean functions. For depth-3 circuits, we prove a lower bound O(n log n) for the size of any circuit computing the cyclic convolution. For depth-2 circuits, a lower bound Ω(n~(3/2)) for the same function was obtained in our previous paper. Here we present an improved proof of this bound. Both lower bounds are the best known for depth-3 and depth-2 circuits, respectively.