On a decomposition of Boolean functions

A special $(s,d,\varepsilon)$-decomposition of an arbitrary Boolean function $f$ of $n$ variables is considered. The elements of the decomposition are $s$, $s<n$, partial functions, each defined on a domain of cardinality $d$, where it coincides with $f$. The minimum possible $d$ is at most $n^3$ times greater than the circuit size of $f$.
Criteria for the existence of $(s,d,\varepsilon)$-decompositions are obtained, and the properties of the latter are examined.
The research was supported by the Russian Foundation for Basic Research, grant 99–01–01175, and by the Federal Program ‘Integration’, grant 473.