Sensitivity of Rotation Symmetric Boolean Functions via Binary Necklaces
Yuan Li, Jing Zhang
Source abstract
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.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.