On the complexity of restrictions of Boolean functions

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.