Geodesic
On the complexity of restrictions of Boolean functions
Diskretnaya Matematika, Tome 8 (1996) no. 2, pp. 133-150 
A. V. Chashkin. On the complexity of restrictions of Boolean functions. Diskretnaya Matematika, Tome 8 (1996) no. 2, pp. 133-150. http://geodesic.mathdoc.fr/item/DM_1996_8_2_a9/
@article{DM_1996_8_2_a9,
     author = {A. V. Chashkin},
     title = {On the complexity of restrictions of {Boolean} functions},
     journal = {Diskretnaya Matematika},
     pages = {133--150},
     year = {1996},
     volume = {8},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1996_8_2_a9/}
}
TY  - JOUR
AU  - A. V. Chashkin
TI  - On the complexity of restrictions of Boolean functions
JO  - Diskretnaya Matematika
PY  - 1996
SP  - 133
EP  - 150
VL  - 8
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DM_1996_8_2_a9/
LA  - ru
ID  - DM_1996_8_2_a9
ER  - 
%0 Journal Article
%A A. V. Chashkin
%T On the complexity of restrictions of Boolean functions
%J Diskretnaya Matematika
%D 1996
%P 133-150
%V 8
%N 2
%U http://geodesic.mathdoc.fr/item/DM_1996_8_2_a9/
%G ru
%F DM_1996_8_2_a9

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

We study the complexity of restrictions of Boolean functions provided that they are realized by circuits of functional elements, contact circuits, formulae and $\pi$-circuits. Let $D(d)=\break\{D\subseteq \{0,1\}^n\mid |D|=d\}$. For sufficiently wide range of values of the parameter $d$ for an arbitrary Boolean function $f$ we give lower bounds of complexity of the most complex of its restrictions on regions of $D(d)$. We discuss the connection between the complexity of partial and completely defined Boolean functions.The work was supported by the Russian Foundation for Basic Researches, Grant 93–011–1527.