Skip to content

Sensitivity and Block Sensitivity of Elementary Symmetric Boolean Functions of Arbitrary Degree

Sep 2026 · arXiv.org · Vol abs/2609.23781 · 2 citations · 12 references
Computer Science Mathematics

Abstract

Let $\sigma_{n,d}$ denote the elementary symmetric Boolean function of $n$ variables and degree $d$. We completely determine the sensitivity, average sensitivity, and block sensitivity of $\sigma_{n,d}$ for every $1\le d\le n$. Using Lucas'theorem, we obtain a uniform binary description of the Hamming-weight value sequence, from which the sensitivity and average-sensitivity formulas follow and the computation of block sensitivity reduces to at most four explicit candidates. Combining these results with the arbitrary-degree formula for certificate complexity, we determine the exact relations among sensitivity, block sensitivity, and certificate complexity. We also prove a general result for symmetric Boolean functions: every nonconstant symmetric Boolean function $f$ satisfies \[ \bs(f)\le \max\{s(f),C(f)-1\}. \] Consequently, only the three patterns \[ s=\bs=C,\qquad s=\bs<C,\qquad s<\bs<C \] can occur for nonconstant symmetric Boolean functions. For elementary symmetric Boolean functions, we give necessary and sufficient conditions for each of these three patterns, thereby completely classifying the relations among $s(\sigma_{n,d})$, $\bs(\sigma_{n,d})$, and $C(\sigma_{n,d})$. In particular, we obtain a necessary and sufficient characterization of the full strict hierarchy \[ s(\sigma_{n,d})<\bs(\sigma_{n,d})<C(\sigma_{n,d}), \] and exhibit infinite families for which it holds.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.