Block Sensitivity and Certificate Complexity of Rotation Symmetric Boolean Functions

Source abstract

We study block sensitivity and certificate complexity of rotation symmetric Boolean functions, with particular emphasis on monomial rotation symmetric Boolean functions. We first show that every odd-degree monomial rotation symmetric Boolean function on $n$ variables satisfies $s=bs=C=n$. We then determine sensitivity, block sensitivity, and certificate complexity for every quadratic monomial rotation symmetric Boolean function. For the quadratic function $Q_{n,k}$ generated by $x_0x_k$, we prove, outside the short-orbit case, that $$C(Q_{n,k})= \begin{cases} n,&4\mid n/\gcd(n,k),\\ n-\gcd(n,k),&4\nmid n/\gcd(n,k). \end{cases}$$ Moreover, $bs(Q_{n,k})=C(Q_{n,k})$ for every quadratic MRS function, and outside the short-orbit case, strict separation $s<bs=C$ occurs exactly when $$\frac{n}{\gcd(n,k)}\equiv2\pmod4.$$ Finally, for the consecutive quartic family $$R_n(x)=\bigoplus_{i\in\mathbb Z_n}x_ix_{i+1}x_{i+2}x_{i+3},$$ we determine all three measures in every residue class modulo $6$, using the sensitivity formulas and, in one residue class, finite-state results established in our companion preprint~\cite{LiZhangRSBFSensitivity}. In particular, for $r=2,3$ and $6q+r\ge5$ we obtain strict separation, $$\boxed{s(R_{6q+r})=6q<bs(R_{6q+r})=C(R_{6q+r})=6q+1,\qquad r=2,3.}$$ Thus this family gives an infinite collection of rotation symmetric Boolean functions for which sensitivity is strictly smaller than block sensitivity, while block sensitivity and certificate complexity coincide.