Block Sensitivity and Certificate Complexity of Rotation Symmetric Boolean Functions
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 Qn,k generated by x0xk, we prove, outside the short-orbit case, that C(Qn,k)= n,&4| n/gcd(n,k), n−gcd(n,k),&4nmid n/gcd(n,k). Moreover, bs(Qn,k)=C(Qn,k) for every quadratic MRS function, and outside the short-orbit case, strict separation s<bs=C occurs exactly when n/gcd(n,k)≡2pmod4. Finally, for the consecutive quartic family Rn(x)=⨁i∈ℤnxixi+1xi+2xi+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≥5 we obtain strict separation, boxeds(R6q+r)=6q<bs(R6q+r)=C(R6q+r)=6q+1, 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.
Related
- Certificate Complexity of Elementary Symmetric Boolean Functions of Arbitrary Degree
- Sensitivity of Rotation Symmetric Boolean Functions via Binary Necklaces
- Sensitivity and Block Sensitivity of Elementary Symmetric Boolean Functions of Arbitrary Degree
- Planar Obliquely Reflected BSVIs on General Filtered Spaces: Non-Symmetric Rotation Fields and Associated Control Problems
- Conservative CSPs in Logspace are in Symmetric Linear Datalog (under complexity theoretic assumptions)
BibTeX
@misc{li2026block,
title = {{Block Sensitivity and Certificate Complexity of Rotation Symmetric Boolean Functions}},
author = {Yuan Li and Jing Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.17100},
eprint = {2610.17100},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.17100},
note = {CC0},
}
RIS
TY - UNPB
TI - Block Sensitivity and Certificate Complexity of Rotation Symmetric Boolean Functions
AU - Yuan Li
AU - Jing Zhang
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.17100
UR - https://arxiv.org/abs/2610.17100
AB - 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)= n,&4| n/gcd(n,k), n−gcd(n,k),&4nmid n/gcd(n,k). 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 n/gcd(n,k)≡2pmod4. Finally, for the consecutive quartic family R_n(x)=⨁_i∈ℤ_nx_ix_i+1x_i+2x_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≥5 we obtain strict separation, boxeds(R_6q+r)=6q<bs(R_6q+r)=C(R_6q+r)=6q+1, 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.
ER -