On the distribution of sensitivities of symmetric Boolean functions

2023/06/26 by Jon T. Butler, Butler, Jon T., Tsutomu Sasao +3
Computer Science · #Coding theory and cryptography #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Quantum Computing Algorithms and Architecture #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2306.14401

openalex publication_date 2023/06/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A Boolean function f( x) is sensitive to bit x_i if there is at least one input vector x and one bit x_i in x, such that changing x_i changes f. A function has sensitivity s if among all input vectors, the largest number of bits to which f is sensitive is s. We count the n-variable symmetric Boolean functions that have maximum sensitivity. We show that most such functions have the largest possible sensitivity, n. This suggests sensitivity is limited as a complexity measure for symmetric Boolean functions.

Related

• Sensitivity versus block sensitivity of Boolean functions
• Tighter Relations Between Sensitivity and Other Complexity Measures
• On the Sensitivity of Cyclically-Invariant Boolean Functions
• Degree and Sensitivity: tails of two distributions
• On the Sensitivity Conjecture for Disjunctive Normal Forms