For Boolean functions f:01n01 and g:01m01 , the function composition of f and g denoted by fg:01nm01 is the value of f on n inputs, each of them is the calculation of g on a distinct set of m Boolean variables. Motivated by previous works that achieved some of the best separations between complexity measures such as sensitivity, block-sensitivity, degree, certificate complexity and decision tree complexity we show that most of these complexity measures behave multiplicatively under composition. We use this multiplicative behavior to establish several applications.

First, we give a negative answer for Adam Kalai's question from [MOS04]: ``Is it true that every Boolean function f:01n01 with degree as a polynomial over the reals (denoted by deg(f)) at most n3 , has a restriction fixing 2n3 of its variables under which f becomes a parity function?'' This question was motivated by the problem of learning juntas as it suggests a simple algorithm, faster than that of Mossel et al. We give a counterexample for the question using composition of functions strongly related to the Walsh-Hadamard code. In fact, we show that for every constants 0">0 there are (infinitely many) Boolean functions f:01n01 such that deg(f)n and under any restriction fixing less than (1−)n variables, f does not become a parity function.

Second, we show that for composition, the block sensitivity (denoted by bs) property has an unusual behavior - namely that bs(fg) can be larger than bs(f)bs(g). We show that the ratio between these two has a strong connection to the integrality gap of the Set Packing problem. In addition, we obtain the best known separation between block-sensitivity and certificate complexity (denoted by C) giving infinitely many functions f such that C(f)bs(f)log(26)log(17)=bs(f)1149 .

Last, we present a factor 2 improvement of a result by Nisan and Szegedy [NS94], by showing that for all Boolean functions bs(f)deg(f)2.