Nisan and Szegedy's Sensitivity Conjecture

Let $f:\{0,1\}^n\rightarrow\{0,1\}$ be a Boolean function. Its sensitivity $s(f)$ is the maximum, over inputs $x$, of the number of coordinates whose individual flip changes $f(x)$. Its block sensitivity $bs(f)$ is the maximum, over inputs $x$, of the number of pairwise disjoint subsets of coordinates whose simultaneous flips change $f(x)$.

Nisan and Szegedy's Sensitivity Conjecture. There exist constants $c$ and $k$ such that for every Boolean function $f$,

$$bs(f)\leq c\cdot s(f)^k.$$

The conjecture says that sensitivity and block sensitivity are polynomially related and is a central question in Boolean-function complexity. The paper treats it as unresolved and studies a lattice variant that implies it.