Block Sensitivity and Certificate Complexity of Rotation Symmetric Boolean Functions
We study block sensitivity and certificate complexity of rotation symmetric Boolean functions, with particular emphasis on monomial rotation symmetric Boolean functions. We first show that every odd-degree monomial rotation symmetric Boolean function on $n$ variables satisfies $s=bs=C=n$. We then determine sensitivity, block sensitivity, and certificate complexity for every quadratic monomial rotation symmetric Boolean function. For the quadratic function $Q_{n,k}$ generated by $x_0x_k$, we prove, outside the short-orbit case, that \[ C(Q_{n,k})= \begin{cases} n,&4\mid n/\gcd(n,k),\\…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.17100
curl -X POST /api/v1/records/arxiv/2610.17100/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.17100/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'