Sensitivity of Rotation Symmetric Boolean Functions via Binary Necklaces

@misc{li2026sensitivity,
  title = {{Sensitivity of Rotation Symmetric Boolean Functions via Binary Necklaces}},
  author = {Yuan Li and Jing Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.17006},
  eprint = {2610.17006},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.17006},
  note = {CC0},
}

TY  - UNPB
TI  - Sensitivity of Rotation Symmetric Boolean Functions via Binary Necklaces
AU  - Yuan Li
AU  - Jing Zhang
PY  - 2026
DA  - 2026/10/12
PB  - arXiv
DO  - 10.48550/arxiv.2610.17006
UR  - https://arxiv.org/abs/2610.17006
AB  - Rotation symmetric Boolean functions are Boolean functions invariant under cyclic permutation of their variables and can be represented by binary necklaces. We express local sensitivity as a weighted bichromatic degree in the necklace quotient and derive an exact formula for the multiplicities between neighboring necklaces. For an odd prime number of variables, we obtain explicit sensitivity formulas and show that multiplicity corrections occur only on an asymptotically negligible family of necklaces. For monomial rotation symmetric Boolean functions, we prove that every odd-degree function has maximum sensitivity, determine the sensitivity of every quadratic function, and determine the sensitivity of the consecutive quartic family. We also determine exactly the sensitivity of cyclic run-threshold functions for arbitrary length and threshold.
ER  -