Geodesic
Functional approximations in the theory of lower bounds for circuit complexity
Diskretnaya Matematika, Tome 2 (1990) no. 2, pp. 45-59.

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

A method for obtaining lower bounds for the complexity of gate circuits by construction of compressed semimetrics in algebras of realizable schemes of objects is recommended. The method allows one to obtain superpolynomial lower bounds for monotone circuits and certain new bounds for other (nonmonotone) circuits. A lower bound $\exp((\log_2 n)^2)$ for a certain class of circuits over the basis $\{\,\vee,^-\}$ and a lower bound of order $\exp(n^{1/4})$ for circuits over certain three-valued extensions of the basis $\{\,\vee,^-\}$ are given. 
@article{DM_1990_2_2_a3,
     author = {S. P. Yukna},
     title = {Functional approximations in the theory of lower bounds for circuit complexity},
     journal = {Diskretnaya Matematika},
     pages = {45--59},
     publisher = {mathdoc},
     volume = {2},
     number = {2},
     year = {1990},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1990_2_2_a3/}
}
TY  - JOUR
AU  - S. P. Yukna
TI  - Functional approximations in the theory of lower bounds for circuit complexity
JO  - Diskretnaya Matematika
PY  - 1990
SP  - 45
EP  - 59
VL  - 2
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_1990_2_2_a3/
LA  - ru
ID  - DM_1990_2_2_a3
ER  - 
%0 Journal Article
%A S. P. Yukna
%T Functional approximations in the theory of lower bounds for circuit complexity
%J Diskretnaya Matematika
%D 1990
%P 45-59
%V 2
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_1990_2_2_a3/
%G ru
%F DM_1990_2_2_a3
S. P. Yukna. Functional approximations in the theory of lower bounds for circuit complexity. Diskretnaya Matematika, Tome 2 (1990) no. 2, pp. 45-59. http://geodesic.mathdoc.fr/item/DM_1990_2_2_a3/