Composition limits and separating examples for some Boolean function complexity measures

Abstract

Block sensitivity ($bs(f)$), certificate complexity ($C(f)$) and fractional certificate complexity ($C^{\ast }(f)$) are three fundamental combinatorial measures of complexity of a boolean function $f$. It has long been known that $bs(f)\le C^{\ast }(f)\le 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)\le 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 $b{s}^{\lim }(f)=(C^{\ast }{)}^{\lim }(f)$ and characterize $s^{\lim }(f),(C^{\ast }{)}^{\lim }(f)$, and $C^{\lim }(f)$ in terms of the largest eigenvalue of a certain set of $2\times 2$ matrices associated with $f$.

Appearing in CCC 2013, 36 pages

Cited by in corpus (1)

• A communication game related to the sensitivity conjecture