Aaronson's lattice variant of the Sensitivity Conjecture
Aaronson's lattice variant of the Sensitivity Conjecture
Let be a two-coloring of the -dimensional lattice . It is non-trivial if the origin is red and there is at least one blue point on each axis. For a point , let be the number of neighbors of with the opposite color, and let be the maximum of over all points.
Aaronson's lattice variant. There exist constants and such that for every non-trivial coloring ,
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.