Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR12-089 | 7th July 2012 04:42

Lattice Variant of the Sensitivity Conjecture


Authors: Meena Boppana
Publication: 7th July 2012 14:22
Downloads: 3041


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.

ISSN 1433-8092 | Imprint