The well-known Sensitivity Conjecture regarding combinatorial complexity measures on Boolean functions states that for any Boolean function $f:\{0,1\}^n \to \{0,1\}$, block sensitivity of $f$ is polynomially related to sensitivity of $f$ (denoted by $\mathbf{sens}(f)$). From the complexity theory side, the XOR Log-Rank Conjecture states that for any Boolean function, $f:\{0,1\}^n \to \{0,1\}$ the communication complexity of a related function $f^{\oplus}:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}$, (defined as $f^{\oplus}(x,y) = f(x \oplus y)$) is bounded by polynomial in logarithm of the sparsity of $f$ (the number of non-zero Fourier coefficients for $f$, denoted by $\mathbf{sparsity}(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 $\mathbf{alt}(f)$) for all Boolean functions $f$ by polynomial in $\mathbf{sens}(f)$ and logarithm of $\mathbf{sparsity}(f)$, respectively. In this context, we show the following results:

* We show that there exists a family of Boolean functions for which $\mathbf{alt}(f)$ is at least \textit{exponential} in $\mathbf{sens}(f)$ and $\mathbf{alt}(f)$ is at least \textit{exponential} in $\log\mathbf{sparsity}(f)$. En route to the proof, we also show an exponential gap between $\mathbf{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 $\mathbf{alt}(f)$ and $\log\mathbf{sparsity}(f)$, the XOR Log-Rank Conjecture is true for functions with the alternation upper bounded by $poly(\log n)$. 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 $f$, $\mathbf{deg}(f) \le \mathbf{alt}(f)\mathbf{deg_2}(f)\mathbf{deg_m}(f)$ where $\mathbf{deg}(f)$, $\mathbf{deg_2}(f)$ and $\mathbf{deg_m}(f)$ are the degrees of $f$ over $\mathbb{R}$, $\mathbb{F}_2$ and $\mathbb{Z}_m$ respectively. We give three further applications of this bound:
1. We show that for Boolean functions $f$ of constant alternation have $\mathbf{deg_2}(f) = \Omega(\log n)$.
2. Moreover, these functions also have high sparsity, thus partially answering a question of Kulkarni and Santha (2013).
3. We observe that our relation also improves the upper bound for influence to $\mathbf{deg_2}(f)^2 \cdot \mathbf{alt}(f)$ improving Guo and Komargodski (2017).

Journal version

The well-known Sensitivity Conjecture regarding combinatorial complexity measures on Boolean functions states that for any Boolean function $f:\{0,1\}^n \to \{0,1\}$, block sensitivity of $f$ is polynomially related to sensitivity of $f$ (denoted by $\mathbf{sens}(f)$). From the complexity theory side, the XOR Log-Rank Conjecture states that for any Boolean function, $f:\{0,1\}^n \to \{0,1\}$ the communication complexity of a related function $f^{\oplus}:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}$, (defined as $f^{\oplus}(x,y) = f(x \oplus y)$) is bounded by polynomial in logarithm of the sparsity of $f$ (the number of non-zero Fourier coefficients for $f$, denoted by $\mathbf{sparsity}(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 $\mathbf{alt}(f)$) for all Boolean functions $f$ by polynomial in $\mathbf{sens}(f)$ and logarithm of $\mathbf{sparsity}(f)$, respectively. In this context, we show the following results:

* We show that there exists a family of Boolean functions for which $\mathbf{alt}(f)$ is at least \textit{exponential} in $\mathbf{sens}(f)$ and $\mathbf{alt}(f)$ is at least \textit{exponential} in $\log\mathbf{sparsity}(f)$. En route to the proof, we also show an exponential gap between $\mathbf{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 $\mathbf{alt}(f)$ and $\log\mathbf{sparsity}(f)$, the XOR Log-Rank Conjecture is true for functions with the alternation upper bounded by $poly(\log n)$. 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 $f$, $\mathbf{deg}(f) \le \mathbf{alt}(f)\mathbf{deg_2}(f)\mathbf{deg_m}(f)$ where $\mathbf{deg}(f)$, $\mathbf{deg_2}(f)$ and $\mathbf{deg_m}(f)$ are the degrees of $f$ over $\mathbb{R}$, $\mathbb{F}_2$ and $\mathbb{Z}_m$ respectively. We give three further applications of this bound:
1. We show that for Boolean functions $f$ of constant alternation have $\mathbf{deg_2}(f) = \Omega(\log n)$.
2. Moreover, these functions also have high sparsity, thus partially answering a question of Kulkarni and Santha (2013).
3. We observe that our relation also improves the upper bound for influence to $\mathbf{deg_2}(f)^2 \cdot \mathbf{alt}(f)$ improving Guo and Komargodski (2017).