Aaronson's lattice variant of the Sensitivity Conjecture

Let CC be a two-coloring of the dd-dimensional lattice Zd\mathbb{Z}^d. It is non-trivial if the origin is red and there is at least one blue point on each axis. For a point xx, let s(C,x)s(C,x) be the number of neighbors of xx with the opposite color, and let s(C)s(C) be the maximum of s(C,x)s(C,x) over all points.

Aaronson's lattice variant. There exist constants cc and kk such that for every non-trivial coloring CC,

dcs(C)k.d \leq c\cdot s(C)^k.

This variant asserts that the dimension and lattice sensitivity are polynomially related, and Aaronson showed that it implies the Boolean Sensitivity Conjecture. The paper studies reductions and constructions relevant to this conjecture, but does not report a resolution.

Sources & referencesView supporting material

Primary source

Meena Boppana, “Lattice Variant of the Sensitivity Conjecture”, arXiv:1207.1824 (2012).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.