In this paper, we study the Boolean function parameters sensitivity (), block sensitivity (), and alternation () under specially designed affine transforms and show several applications. For a function , and for and , the result of the transformation g is defined as .
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 ). By a result of Lin and Zhang (2017) , it follows that . Thus, to settle the Sensitivity Conjecture (), it suffices to argue that . However, we exhibit an explicit family of Boolean functions for which is .
Going further, we use an affine transform A, such that the corresponding function g satisfies . We apply this in the setting of quantum communication complexity to prove that for , the bounded error quantum communication complexity of F with prior entanglement, ⁎ is . 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 ϵ, , any Boolean function f that depends on all its inputs with must satisfy ⁎. Here, denotes the degree of the multilinear polynomial over which agrees with f on Boolean inputs.
For Boolean function f such that there exists primes p and q with for , the deterministic communication complexity - and ⁎ are polynomially related. In particular, this holds when . Thus, for this class of functions, this answers an open question (see Buhrman and de Wolf (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, . Using this new relation, we exhibit Boolean functions f (other than the parity function) such that is where 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 (2019) ).