Certificate Complexity of Elementary Symmetric Boolean Functions of Arbitrary Degree

Source abstract

Let $σ_{n,d}$ denote the elementary symmetric Boolean function of $n$ variables and degree $d$. Our previous work determined its certificate complexity when $d$ is odd and when $d$ is a power of $2$, while even degrees with at least two nonzero binary digits were left open. We solve that open question and determine $C(σ_{n,d})$ for every $1\le d\le n$.