Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements
D. Yu. Cherukhin · Discrete Mathematics and Applications · 2011
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 ≥ 2 are of the form Ω( nλ d –1 ( n )). In particular, for d = 2, 3, 4 they are of the form Ω( n 3/2 ), Ω( n log n ), and Ω( n log log n ) respectively; for d ≥ 5 the function λ 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.