For Boolean functions $f:\{0,1\}^n \to \{0,1\}$ and $g:\{0,1\}^m \to \{0,1\}$, the function composition of $f$ and $g$ denoted by $f\circ g : \{0,1\}^{nm} \to \{0,1\}$ 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:\{0,1\}^n\to\{0,1\}$ with degree as a polynomial over the reals (denoted by $\deg(f)$) at most $n/3$, has a restriction fixing $2n/3$ 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 $\epsilon,\delta>0$ there are (infinitely many) Boolean functions $f: \{0,1\}^n \to \{0,1\}$ such that $\deg(f) \le \epsilon \cdot n$ and under any restriction fixing less than $(1-\delta) \cdot n$ variables, $f$ does not become a parity function.

Second, we show that for composition, the block sensitivity (denoted by $\mathrm{bs}$) property has an unusual behavior - namely that $\mathrm{bs}(f\circ g)$ can be larger than ${\mathrm{bs}}(f) \cdot {\mathrm{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 ${\mathrm{C}}$) giving infinitely many functions $f$ such that ${\mathrm{C}}(f) \ge {\mathrm{bs}}(f)^{\log(26)/\log(17)} = {\mathrm{bs}}(f)^{1.149\ldots}$.

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