Summary
This paper looks at special Boolean functions called elementary symmetric functions, which depend on how many input variables are set to true. Previously, the authors found how complex it is to verify these functions for some cases, but not all. Now they solve that problem, describing exactly how complex it is for every possible case. This helps complete the understanding of these functions’ verification difficulty.
What this means in practice
- •For complexity theorists: Clarify exact verification costs for symmetric Boolean functions across all degrees to inform complexity class boundaries.
- •For cryptographic algorithm designers: Use precise certificate complexity data to assess hardness assumptions in protocols involving symmetric Boolean functions.
A theory result. No direct application yet.
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$.