Block Sensitivity and Certificate Complexity of Rotation Symmetric Boolean Functions

Source: arxiv.org/abs/2610.17100

Yuan Li, Jing Zhang

arXivarxiv/2610.17100Oct 12, 2026math.COscore 0

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),\\…

JSON

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}'