Certificate Complexity of Elementary Symmetric Boolean Functions of Arbitrary Degree
Let $σ_{n,d}$ denote the elementary symmetric Boolean function of $n$ variables and degree $d$. Previous work determined $C(σ_{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 completing the classification for elementary symmetric Boolean functions. Writing $d=2^t m$ with $m$ odd, we obtain an explicit formula in which the possible deficit from the maximal value $n$ is controlled by $2^t$, while the exact value is determined by a binary containment condition…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.15678
curl -X POST /api/v1/records/arxiv/2609.15678/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.15678/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'