Alternation, Sparsity and Sensitivity : Bounds and Exponential Gaps
arXiv:1712.05735 · doi:10.1016/j.tcs.2018.11.015
Abstract
The well-known Sensitivity Conjecture states that for any Boolean function , block sensitivity of is at most polynomial in sensitivity of (denoted by $\s(f)$). The XOR Log-Rank Conjecture states that for any bit Boolean function, the communication complexity of a related function on bits, (defined as ) is at most polynomial in logarithm of the sparsity of (denoted by $\sp(f)$). A recent result of Lin and Zhang (2017) implies that to confirm the above conjectures it suffices to upper bound alternation of (denoted $\al(f)$) for all Boolean functions by polynomial in $\s(f)$ and logarithm of $\sp(f)$, respectively. In this context, we show the following : * There exists a family of Boolean functions for which $\al(f)$ is at least exponential in $\s(f)$ and $\al(f)$ is at least exponential in $\log \sp(f)$. En route to the proof, we also show an exponential gap between $\al(f)$ and the decision tree complexity of , which might be of independent interest. * As our main result, we show that, despite the above gap between $\al(f)$ and $\log \sp(f)$, the XOR Log-Rank Conjecture is true for functions with the alternation upper bounded by . It is easy to observe that the Sensitivity Conjecture is also true for this class of functions. * The starting point for the above result is the observation (derived from Lin and Zhang (2017)) that for any Boolean function and , $deg(f)\le \al(f)deg_2(f)deg_m(f)$ where , and are the degrees of over , and respectively. We also show three further applications of this observation.
19 pages, 1 figure, Journal version