Geodesic
Depth of Boolean functions realized by circuits over an arbitrary infinite basis
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 6 (2012), pp. 55-57 
O. M. Kasim-zade. Depth of Boolean functions realized by circuits over an arbitrary infinite basis. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 6 (2012), pp. 55-57. http://geodesic.mathdoc.fr/item/VMUMM_2012_6_a11/
@article{VMUMM_2012_6_a11,
     author = {O. M. Kasim-zade},
     title = {Depth of {Boolean} functions realized by circuits over an arbitrary infinite basis},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {55--57},
     year = {2012},
     number = {6},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2012_6_a11/}
}
TY  - JOUR
AU  - O. M. Kasim-zade
TI  - Depth of Boolean functions realized by circuits over an arbitrary infinite basis
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2012
SP  - 55
EP  - 57
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2012_6_a11/
LA  - ru
ID  - VMUMM_2012_6_a11
ER  - 
%0 Journal Article
%A O. M. Kasim-zade
%T Depth of Boolean functions realized by circuits over an arbitrary infinite basis
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2012
%P 55-57
%N 6
%U http://geodesic.mathdoc.fr/item/VMUMM_2012_6_a11/
%G ru
%F VMUMM_2012_6_a11

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

Bounds for the circuit depth of all Boolean functions tight up to a small additive constant are obtained for all infinite bases.

[1] Lupanov O.B., “O skhemakh iz funktsionalnykh elementov s zaderzhkami”, Problemy kibernetiki, 23, Nauka, M., 1970, 43–81

[2] Savage J.E., The complexity of computing, Wiley, N.Y., 1976 ; Sevedzh Dzh.E., Slozhnost vychislenii, Faktorial, M., 1998 | MR

[3] Kasim-Zade O.M., “O glubine bulevykh funktsii pri realizatsii skhemami nad proizvolnym bazisom”, Vestn. Mosk. un-ta. Matem. Mekhan., 2007, no. 1, 18–21

[4] Kasim-Zade O.M., “O glubine bulevykh funktsii nad proizvolnym beskonechnym bazisom”, Diskretnyi analiz i issledovanie operatsii. Ser. 1, 14:1 (2007), 45–69

[5] Smolensky R., “Algebraic methods in the theory of lower bounds for Boolean circuit complexity”, Proc. 19th Annual ACM Symp. Theory Comput., ACM Press, N.Y., 1987, 77–82

[6] Boppana R.B., Sipser M., “The complexity of finite functions”, Handbook of Theoretical Computer Science, v. A, Algorithms and complexity, ed. J. van Leeuwen, Elsevier, Amsterdam, 1990, 757–804 | MR