|
This article is cited in 1 scientific paper (total in 1 paper)
Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements
D. Yu. Cherukhin
Abstract:
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.
Received: 25.02.2009
Citation:
D. Yu. Cherukhin, “Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements”, Diskr. Mat., 23:4 (2011), 39–47; Discrete Math. Appl., 21:4 (2011), 499–508
Linking options:
https://www.mathnet.ru/eng/dm1160https://doi.org/10.4213/dm1160 https://www.mathnet.ru/eng/dm/v23/i4/p39
|
Statistics & downloads: |
Abstract page: | 438 | Full-text PDF : | 195 | References: | 49 | First page: | 27 |
|