pdf icon
Theory of Computing Library
Graduate Surveys 4
Variations on the Sensitivity Conjecture
Published: June 22, 2011    (27 pages)
Keywords: sensitivity, block sensitivity, complexity measures of Boolean functions
ACM Classification: F.1.2, F.2.2
AMS Classification: 05D99

Abstract: [Plain Text Version]

The sensitivity of a Boolean function $f$ of $n$ Boolean variables is the maximum over all inputs $x$ of the number of positions $i$ such that flipping the $i$-th bit of $x$ changes the value of $f(x)$. Permitting to flip disjoint blocks of bits leads to the notion of block sensitivity, known to be polynomially related to a number of other complexity measures of $f$, including the decision-tree complexity, the polynomial degree, and the certificate complexity. A long-standing open question is whether sensitivity also belongs to this equivalence class. A positive answer to this question is known as the Sensitivity Conjecture. We present a selection of known as well as new variants of the Sensitivity Conjecture and point out some weaker versions that are also open. Among other things, we relate the problem to Communication Complexity via recent results by Sherstov (QIC 2010). We also indicate new connections to Fourier analysis.