Geodesic
On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates
Diskretnaya Matematika, Tome 30 (2018) no. 2, pp. 120-137

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

We obtain estimates for the complexity of the implementation of $n$-place Boolean functions by circuits and formulas built of unbounded fan-in conjunction and disjunction gates and either negation gates or negations of variables as inputs. Restrictions on the depth of circuits and formulas are imposed. In a number of cases, the estimates obtained in the paper are shown to be asymptotically sharp. In particular, for the complexity of circuits with variables and their negations on inputs, the Shannon function is asymptotically estimated as $2\cdot2^{n/2}$; this estimate is attained on depth-3 circuits.
Keywords: bounded-depth circuits, complexity, Boolean cube partitions. 
@article{DM_2018_30_2_a8,
     author = {I. S. Sergeev},
     title = {On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates},
     journal = {Diskretnaya Matematika},
     pages = {120--137},
     publisher = {mathdoc},
     volume = {30},
     number = {2},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2018_30_2_a8/}
}
TY  - JOUR
AU  - I. S. Sergeev
TI  - On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates
JO  - Diskretnaya Matematika
PY  - 2018
SP  - 120
EP  - 137
VL  - 30
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2018_30_2_a8/
LA  - ru
ID  - DM_2018_30_2_a8
ER  - 
%0 Journal Article
%A I. S. Sergeev
%T On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates
%J Diskretnaya Matematika
%D 2018
%P 120-137
%V 30
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2018_30_2_a8/
%G ru
%F DM_2018_30_2_a8
I. S. Sergeev. On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates. Diskretnaya Matematika, Tome 30 (2018) no. 2, pp. 120-137. http://geodesic.mathdoc.fr/item/DM_2018_30_2_a8/