{"id":"arxiv/2609.23781","url":"https://arxiv.org/abs/2609.23781","tags":["math.CO","cs.DM"],"score":0,"title":"Sensitivity and Block Sensitivity of Elementary Symmetric Boolean Functions of Arbitrary Degree","domain":"math.CO","source":"arxiv","authors":["Yuan Li","Jing Zhang"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-20","reactions":{}}