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 sequ...
Let $\sigma_{n,d}$ denote the elementary symmetric Boolean function of $n$ variables and degree $d$. Previous work determined $C(\sigma_{n,d})$ when $d$ is odd or a power of two, but the general even non-power-of-two case remained open. We determine the certificate complexity for every degree $1\le d\le n$, thereby com...
Let $\sigma_{n,d}$ denote the elementary symmetric Boolean function of $n$ variables and degree $d$. Previous work determined $C(\sigma_{n,d})$ when $d$ is odd or a power of two, but the general even non-power-of-two case remained open. We determine the certificate complexity for every degree $1\le d\le n$, thereby com...