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

@misc{li2026sensitivity,
  title = {{Sensitivity and Block Sensitivity of Elementary Symmetric Boolean Functions of Arbitrary Degree}},
  author = {Yuan Li and Jing Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.23781},
  eprint = {2609.23781},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.23781},
  note = {CC0},
}

TY  - UNPB
TI  - Sensitivity and Block Sensitivity of Elementary Symmetric Boolean Functions of Arbitrary Degree
AU  - Yuan Li
AU  - Jing Zhang
PY  - 2026
DA  - 2026/09/20
PB  - arXiv
DO  - 10.48550/arxiv.2609.23781
UR  - https://arxiv.org/abs/2609.23781
AB  - Let σ_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 σ_n,d for every 1≤ d≤ 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)≤ max{s(f),C(f)−1}. Consequently, only the three patterns s=bs=C, s=bs<C, 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(σ_n,d), bs(σ_n,d), and C(σ_n,d). In particular, we obtain a necessary and sufficient characterization of the full strict hierarchy s(σ_n,d)<bs(σ_n,d)<C(σ_n,d), and exhibit infinite families for which it holds.
ER  -