Geodesic
Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements
Diskretnaya Matematika, Tome 23 (2011) no. 4, pp. 39-47.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DM_2011_23_4_a2,
     author = {D. Yu. Cherukhin},
     title = {Lower bounds for complexity of {Boolean} circuits of finite depth with arbitrary elements},
     journal = {Diskretnaya Matematika},
     pages = {39--47},
     publisher = {mathdoc},
     volume = {23},
     number = {4},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2011_23_4_a2/}
}
TY  - JOUR
AU  - D. Yu. Cherukhin
TI  - Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements
JO  - Diskretnaya Matematika
PY  - 2011
SP  - 39
EP  - 47
VL  - 23
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2011_23_4_a2/
LA  - ru
ID  - DM_2011_23_4_a2
ER  - 
%0 Journal Article
%A D. Yu. Cherukhin
%T Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements
%J Diskretnaya Matematika
%D 2011
%P 39-47
%V 23
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2011_23_4_a2/
%G ru
%F DM_2011_23_4_a2
D. Yu. Cherukhin. Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements. Diskretnaya Matematika, Tome 23 (2011) no. 4, pp. 39-47. http://geodesic.mathdoc.fr/item/DM_2011_23_4_a2/

[1] Valiant L. G., “Graph-theoretic arguments in low-level complexity”, Lecture Notes Computer Sci., 53, 1977, 162–176 | MR | Zbl

[2] Pippenger N., “Superconcentrators of depth 2”, J. Comput. Syst. Sci., 24 (1982), 82–90 | DOI | MR | Zbl

[3] Dolev D., Dwork C., Pippenger N., Wigderson A., “Superconcentrators, generalizers and generalized connectors with limited depth”, Proc. ACM STOC' 83, ACM Press, New York, 1983, 42–51

[4] Radhakrishnan J., Ta-Shma A., “Bounds for dispersers, extractors and depth-two superconcentrators”, SIAM J. Discrete Math., 13 (2000), 2–24 | DOI | MR | Zbl

[5] Alon N., Pudlák P., “Superconcentrators of depth 2 and 3: odd levels help (rarely)”, J. Comput. Syst. Sci., 48 (1994), 194–202 | DOI | MR | Zbl

[6] Pudlák P., “Communication in bounded depth circuits”, Combinatorica, 14 (1994), 203–216 | DOI | MR | Zbl

[7] Pudlák P., Savický P., “On shifting networks”, Theoret. Comput. Sci., 116 (1993), 415–419 | DOI | MR | Zbl

[8] Pudlák P., Rödl V., Sgall J., “Boolean circuits, tensor ranks and communication complexity”, SIAM J. Comput., 26 (1997), 605–633 | DOI | MR | Zbl

[9] Raz R., Shpilka A., “Lower bounds for matrix product in bounded depth circuits with arbitrary gates”, SIAM J. Comput., 32 (2003), 488–513 | DOI | MR | Zbl

[10] Jukna S., “Entropy of operators or why matrix multiplication is hard for depth-two circuits”, Theory Comput. Syst., 46 (2010), 301–310 | DOI | MR | Zbl

[11] Cherukhin D. Yu., “Complexity estimation from below in the class of schemes of depth 2 without restrictions on basis”, Moscow Univ. Math. Bull., 60:4 (2005), 42–44 | MR | Zbl

[12] Cherukhin D. Yu., “Lower bounds for depth-$2$ and depth-3 Boolean circuits with arbitrary gates”, Lecture Notes Comput. Sci., 5010, 2008, 122–133 | MR | Zbl

[13] Zhang Z., Yeung R. W., “On characterization of entropy function via information inequalities”, IEEE Trans. Inform. Theory, 44 (1998), 1440–1450 | DOI | MR