zbMATH — the first resource for mathematics

Lower bounds for depth-2 and depth-3 Boolean circuits with arbitrary gates. (English) Zbl 1142.68364
Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. Third international computer science symposium in Russia, CSR 2008 Moscow, Russia, June 7–12, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79708-1/pbk). Lecture Notes in Computer Science 5010, 122-133 (2008).
Summary: We consider depth-2 and 3 circuits over the basis consisting of all Boolean functions. For depth-3 circuits, we prove a lower bound \(\Omega (n\log n)\) for the size of any circuit computing the cyclic convolution. For depth-2 circuits, a lower bound \(\Omega (n ^{3/2})\) for the same function was obtained in our previous paper [D. Yu. Cherukhin, “A lower bound for the complexity in the class of schemes of depth 2 without restrictions on a basis”, Vestn. Mosk. Univ., Ser. I 2005, No. 4, 54–56 (2005); translation in Mosc. Univ. Math. Bull. 60, No. 4, 42–44 (2005; Zbl 1104.94066)]. Here we present an improved proof of this bound. Both lower bounds are the best known for depth-3 and depth-2 circuits, respectively.
For the entire collection see [Zbl 1136.68005].

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
PDF BibTeX Cite
Full Text: DOI