paper

Block Sensitivity and Certificate Complexity of Rotation Symmetric Boolean Functions

arXiv:2610.17100

Abstract

We investigate block sensitivity and certificate complexity of monomial rotation-symmetric Boolean functions, obtaining exact formulas and structural classifications for several families. For odd-degree monomial rotation-symmetric functions, the equality established in our earlier work yields . For quadratic monomial rotation-symmetric functions, we determine both measures completely and prove that block sensitivity equals certificate complexity. For consecutive quartic monomials, we determine sensitivity, block sensitivity, and certificate complexity in every residue class of the number of variables. Our principal result is an exact global block-sensitivity formula for consecutive monomials of every even degree . Writing , where and , we prove \[ bs(F_{d,n})=n-\min\left\{\left\lceil\fracρ{2}\right\rceil,d+2-ρ\right\}. \] We also establish the corresponding sensitivity formula by a self-contained argument, yielding arbitrarily large gaps between sensitivity and block sensitivity as the degree varies. For certificate complexity, we obtain exact pointwise formulas for structured run-and-gap configurations and establish additional global equalities, including for . Our methods combine cyclic run decomposition, parity arguments, explicit sensitive-block constructions, and constant-subcube certificates. The exact global certificate complexity for arbitrary even degrees remains open.

arXiv commentVersion 2, 44 pages