Graduate Surveys 4

**Keywords:**sensitivity, block sensitivity, complexity measures of Boolean functions

**Categories:**graduate survey, complexity theory, Boolean complexity, sensitivity, communication complexity

**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.