Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements

D. Yu. Cherukhin

Diskretnaya Matematika, Tome 23 (2011) no. 4, pp. 39-47

Résumé

We consider circuits of functional elements of a finite depth whose elements are arbitrary Boolean functions of any number of arguments. We suggest a method of finding nonlinear lower bounds for complexity applicable, in particular, to the operator of cyclic convolution. The obtained lower bounds for the circuits of depth $d\ge2$ are of the form $\Omega(n\lambda_{d-1}(n))$. In particular, for $d=2,3,4$ they are of the form $\Omega(n^{3/2})$, $\Omega(n\log n)$ and $\Omega(n\log\log n)$ respectively; for $d\ge5$ the function $\lambda_{d-1}(n)$ is a slowly increasing function. These lower bounds are the greatest known ones for all even $d$ and for $d=3$. For $d=2,3$, these estimates have been obtained in earlier studies of the author.