  The Sensitivity Conjecture, posed in 1994, states that the fundamental
measures known as the sensitivity and block sensitivity of a Boolean function
f, s(f) and bs(f) respectively, are polynomially related. It is known that
bs(f) is polynomially related to important measures in computer science
including the decision-tree depth, polynomial degree, and parallel RAM
computation time of f, but little is known how the sensitivity compares; the
separation between s(f) and bs(f) is at least quadratic and at most
exponential. We analyze a promising variant by Aaronson that implies the
Sensitivity Conjecture, stating that for all two-colorings of the d-dimensional
lattice $\mathbb{Z}^d$, d and the sensitivity s(C) are polynomially related,
where s(C) is the maximum number of differently-colored neighbors of a point.
We construct a coloring with the largest known separation between d and s(C),
in which $d=O(s(C)^2)$, and demonstrate that it is optimal for a large class of
colorings. We also give a reverse reduction from the Lattice Variant to the
Sensitivity Conjecture, and using this prove the first non-constant lower bound
on s(C). These results indicate that the Lattice Variant can help further the
limited progress on the Sensitivity Conjecture.

Combinatorics;Computational Complexity