In this paper, we study the Boolean function parameters sensitivity ($\mathbf{s}$), block sensitivity ($\mathbf{bs}$), and alternation ($\mathbf{alt}$) under specially designed affine transforms and show several applications. For a function $f:\mathbb{F}_2^n \to \{0,1\}$, and $A = Mx+b$ for $M \in \mathbb{F}_2^{n \times n}$ and $b \in \mathbb{F}_2^n$, the result of the transformation $g$ is defined as $\forall x \in \mathbb{F}_2^n, g(x) = f(Mx+b)$.

As a warm up, we study alternation under linear shifts (when $M$ is restricted to be the identity matrix) called the shift invariant alternation (the smallest alternation that can be achieved for the Boolean function $f$ by shifts, denoted by $\mathbf{salt}(f)$). By a result of Lin and Zhang [ICALP 2017], it follows that $\mathbf{bs}(f) \le O(\mathbf{salt}(f)^2\mathbf{s}(f))$. Thus, to settle the Sensitivity Conjecture ($\forall~f, \mathbf{bs}(f) \le poly(\mathbf{s}(f))$), it suffices to argue that $\forall ~f, \mathbf{salt}(f) \le poly(\mathbf{s}(f))$. However, we exhibit an explicit family of Boolean functions for which $\mathbf{salt}(f)$ is $2^{\Omega(\mathbf{s}(f))}$.

Going further, we use an affine transform $A$, such that the corresponding function $g$ satisfies $\mathbf{bs}(f,0^n) \le \mathbf{s}(g)$, to prove that for $F(x,y) := f(x \land y)$, the bounded error quantum communication complexity of $F$ with prior entanglement, $Q^*_{1/3}(F)$ is $\Omega(\sqrt{\mathbf{bs}(f,0^n)})$. Our proof builds on ideas from Sherstov [Quantum Information and Computation, 10:435–455, 2010] where we use specific properties of the above affine transformation. Using this, we show the following.

* For a fixed prime $p$ and an $\epsilon$, $0 < \epsilon < 1$, any Boolean function $f$ that depends on all its inputs with $\mathbf{deg}_p(f) \le (1-\epsilon)\log n$ must satisfy $Q^*_{1/3}(F) = \Omega\left (\frac{n^{\epsilon/2}}{\log n} \right )$. Here, $\mathbf{deg}_p(f)$ denotes the degree of the multilinear polynomial over $\mathbb{F}_p$ which agrees with $f$ on Boolean inputs.

* For Boolean function $f$ such that there exists primes $p$ and $q$ with $\mathbf{deg}_q(f) \ge \Omega(\mathbf{deg}_p(f)^\delta)$ for $\delta > 2$, the deterministic communication complexity - $\mathbf{D}(F)$ and $Q^*_{1/3}(F)$ are polynomially related. In particular, this holds when $\mathbf{deg}_p(f) = O(1)$. Thus, for this class of functions, this answers an open question (see Buhrman and de Wolf [CCC 2001]) about the relation between the two measures.

Restricting back to the linear setting, we construct linear transformation $A$, such that the corresponding function $g$ satisfies, $\mathbf{alt}(f) \le 2\mathbf{s}(g)+1$. Using this new relation, we exhibit Boolean functions $f$ (other than the parity function) such that $\mathbf{s}(f)$ is $\Omega(\sqrt{\mathbf{sparsity}(f)})$ where $\mathbf{sparsity}(f)$ is the number of non-zero coefficients in the Fourier representation of $f$. This family of Boolean functions also rule out a potential approach to settle the XOR Log-Rank conjecture via the recently settled Sensitivity conjecture [Hao Huang, Annals of Mathematics, 190(3): 949-955, 2019].

Added a new lower bound for shifted alternation (in Section 3) and an application to the existence of family of functions under linear transforms (in Section 5).

In this paper, we study the Boolean function parameters sensitivity ($\mathbf{s}$), block sensitivity ($\mathbf{bs}$), and alternation ($\mathbf{alt}$) under specially designed affine transforms and show several applications. For a function $f:\mathbb{F}_2^n \to \{0,1\}$, and $A = Mx+b$ for $M \in \mathbb{F}_2^{n \times n}$ and $b \in \mathbb{F}_2^n$, the result of the transformation $g$ is defined as $\forall x \in \mathbb{F}_2^n, g(x) = f(Mx+b)$.

As a warm up, we study alternation under linear shifts (when $M$ is restricted to be the identity matrix) called the shift invariant alternation (the smallest alternation that can be achieved for the Boolean function $f$ by shifts, denoted by $\mathbf{salt}(f)$). By a result of Lin and Zhang (2017), it follows that $\mathbf{bs}(f) \le O(\mathbf{salt}(f)^2\mathbf{s}(f))$. Thus, to settle the Sensitivity Conjecture ($\forall~f, \mathbf{bs}(f) \le poly(\mathbf{s}(f))$), it suffices to argue that $\forall~f, \mathbf{salt}(f) \le poly(\mathbf{s}(f))$. However, we exhibit an explicit family of Boolean functions for which $\mathbf{salt}(f)$ is $2^{\Omega(\mathbf{s}(f))}$.

Going further, we use an affine transform $A$, such that the corresponding function $g$ satisfies $\mathbf{bs}(f,0^n) \le \mathbf{s}(g)$, to prove that for $F(x,y) := f(x \land y)$, the bounded error quantum communication complexity of $F$ with prior entanglement, $Q^*_{1/3}(F)$ is $\Omega(\sqrt{\mathbf{bs}(f,0^n)})$. Our proof builds on ideas from Sherstov (2010) where we use specific properties of the above affine transformation. Using this, we show the following.

* For a fixed prime $p$ and an $\epsilon$, $0 < \epsilon < 1$, any Boolean function $f$ that depends on all its inputs with $\mathbf{deg}_p(f) \le (1-\epsilon)\log n$ must satisfy $Q^*_{1/3}(F) = \Omega\left (\frac{n^{\epsilon/2}}{\log n} \right )$. Here, $\mathbf{deg}_p(f)$ denotes the degree of the multilinear polynomial over $\mathbb{F}_p$ which agrees with $f$ on Boolean inputs.

* For Boolean function $f$ such that there exists primes $p$ and $q$ with $\mathbf{deg}_q(f) \ge \Omega(\mathbf{deg}_p(f)^\delta)$ for $\delta > 2$, the deterministic communication complexity - $\mathbf{D}(F)$ and $Q^*_{1/3}(F)$ are polynomially related. In particular, this holds when $\mathbf{deg}_p(f) = O(1)$. Thus, for this class of functions, this answers an open question (see \cite{BW01}) about the relation between the two measures.

Restricting back to the linear setting, we construct linear transformation $A$, such that the corresponding function $g$ satisfies, $\mathbf{alt}(f) \le 2\mathbf{s}(g)+1$. Using this new relation, we exhibit Boolean functions $f$ (other than the parity function) such that $\mathbf{s}(f)$ is $\Omega(\sqrt{\mathbf{sparsity}(f)})$ where $\mathbf{sparsity}(f)$ is the number of non-zero coefficients in the Fourier representation of $f$.