Relationships among sensitivity measures of symmetric Boolean functions
Sensitivity and Block Sensitivity of Elementary Symmetric Boolean Functions of Arbitrary Degree
Discrete Mathematics
Summary
This paper studies how different ways of measuring the complexity of certain logical functions called elementary symmetric Boolean functions relate to each other. The authors find exact formulas for three sensitivity measures—sensitivity, average sensitivity, and block sensitivity—for all degrees of these functions. They also prove general rules that restrict how these measures can be arranged relative to one another. Finally, they completely classify when each pattern of relationships can happen and provide examples where these patterns occur.
What this means in practice
- •For circuit designers: Use exact measures of Boolean function complexity to guide design optimizations for symmetric logic components.
- •For complexity theorists: Employ precise relations among sensitivity measures to analyze or classify symmetric Boolean functions in complexity theory.
A theory result. No direct application yet.
Authors
Yuan Li, Jing Zhang
Abstract
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\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(σ_{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.