In this paper, we study the Boolean function parameters sensitivity ( s ), block sensitivity ( bs ), and alternation ( alt ) under specially designed affine transforms and show several applications. For a function f : F n 2 0 1 , and A = M x + b for M F 2 n n and b F n 2 , the result of the transformation g is defined as x F n 2 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 salt ( f ) ). By a result of Lin and Zhang (2017), it follows that bs ( f ) O ( salt ( f ) 2 s ( f )) . Thus, to settle the Sensitivity Conjecture ( f bs ( f ) p ol y ( s ( f )) ), it suffices to argue that f salt ( f ) p ol y ( s ( f )) . However, we exhibit an explicit family of Boolean functions for which salt ( f ) is 2 ( s ( f )) .

Going further, we use an affine transform A , such that the corresponding function g satisfies bs ( f 0 n ) s ( g ) , to prove that for F ( x y ) : = f ( x y ) , the bounded error quantum communication complexity of F with prior entanglement, Q 1 3 ( F ) is ( 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 , 0 1 , any Boolean function f that depends on all its inputs with de g p ( f ) ( 1 − ) log n must satisfy Q 1 3 ( F ) = n 2 log n . Here, de g p ( f ) denotes the degree of the multilinear polynomial over F p which agrees with f on Boolean inputs.

* For Boolean function f such that there exists primes p and q with de g q ( f ) ( de g p ( f ) ) for 2"> 2 , the deterministic communication complexity - D ( F ) and Q 1 3 ( F ) are polynomially related. In particular, this holds when de g 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, alt ( f ) 2 s ( g ) + 1 . Using this new relation, we exhibit Boolean functions f (other than the parity function) such that s ( f ) is ( sparsit y ( f ) ) where sparsit y ( f ) is the number of non-zero coefficients in the Fourier representation of f .