The well-known Sensitivity Conjecture regarding combinatorial complexity measures on Boolean functions states that for any Boolean function f : 0 1 n 0 1 , block sensitivity of f is polynomially related to sensitivity of f (denoted by sens ( f ) ). From the complexity theory side, the XOR Log-Rank Conjecture states that for any Boolean function, f : 0 1 n 0 1 the communication complexity of a related function f : 0 1 n 0 1 n 0 1 , (defined as f ( x y ) = f ( x y ) ) is bounded by polynomial in logarithm of the sparsity of f (the number of non-zero Fourier coefficients for f , denoted by sparsit y ( f ) ). Both the conjectures play a central role in the domains in which they are studied.

A recent result of Lin and Zhang (2017) implies that to confirm the above two conjectures it suffices to upper bound alternation of f (denoted alt ( f ) ) for all Boolean functions f by polynomial in sens ( f ) and logarithm of sparsit y ( f ) , respectively. In this context, we show the following results:

* We show that there exists a family of Boolean functions for which alt ( f ) is at least \textit{exponential} in sens ( f ) and alt ( f ) is at least \textit{exponential} in log sparsit y ( f ) . En route to the proof, we also show an exponential gap between alt ( f ) and the decision tree complexity of f , which might be of independent interest.

* As our main result, we show that, despite the above exponential gap between alt ( f ) and log sparsit y ( f ) , the XOR Log-Rank Conjecture is true for functions with the alternation upper bounded by pol y ( log n ) . It is easy to observe that the Sensitivity Conjecture is also true for this class of functions.