  Block sensitivity ($bs(f)$), certificate complexity ($C(f)$) and fractional
certificate complexity ($C^*(f)$) are three fundamental combinatorial measures
of complexity of a boolean function $f$. It has long been known that $bs(f)
\leq C^{\ast}(f) \leq C(f) =O(bs(f)^2)$. We provide an infinite family of
examples for which $C(f)$ grows quadratically in $C^{\ast}(f)$ (and also
$bs(f)$) giving optimal separations between these measures. Previously the
biggest separation known was $C(f)=C^{\ast}(f)^{\log_{4.5}5}$. We also give a
family of examples for which $C^{\ast}(f)=\Omega(bs(f)^{3/2})$.
  These examples are obtained by composing boolean functions in various ways.
Here the composition $f \circ g$ of $f$ with $g$ is obtained by substituting
for each variable of $f$ a copy of $g$ on disjoint sets of variables. To
construct and analyse these examples we systematically investigate the
behaviour under function composition of these measures and also the sensitivity
measure $s(f)$. The measures $s(f)$, $C(f)$ and $C^{\ast}(f)$ behave nicely
under composition: they are submultiplicative (where measure $m$ is
submultiplicative if $m(f \circ g) \leq m(f)m(g)$) with equality holding under
some fairly general conditions. The measure $bs(f)$ is qualitatively different:
it is not submultiplicative. This qualitative difference was not noticed in the
previous literature and we correct some errors that appeared in previous
papers. We define the composition limit of a measure $m$ at function $f$,
$m^{\lim}(f)$ to be the limit as $k$ grows of $m(f^{(k)})^{1/k}$, where
$f^{(k)}$ is the iterated composition of $f$ with itself $k$-times. For any
function $f$ we show that $bs^{\lim}(f) = (C^*)^{\lim}(f)$ and characterize
$s^{\lim}(f), (C^*)^{\lim}(f)$, and $C^{\lim}(f)$ in terms of the largest
eigenvalue of a certain set of $2\times 2$ matrices associated with $f$.
