Header menu link for other important links
X
Sensitivity, Affine Transforms and Quantum Communication Complexity
Published in Springer Verlag
2019
Volume: 11653 LNCS
   
Pages: 140 - 152
Abstract
In this paper, we study the Boolean function parameters sensitivity ((Formula Presented) ), block sensitivity ((Formula Presented) ), and alternation ((Formula Presented) ) under specially designed affine transforms and show several applications. For a function (Formula Presented), and (Formula Presented) for (Formula Presented) and (Formula Presented), the result of the transformation g is defined as (Formula Presented). 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 (Formula Presented) ). By a result of Lin and Zhang [12], it follows that (Formula Presented). Thus, to settle the Sensitivity Conjecture ((Formula Presented) ), it suffices to argue that (Formula Presented). However, we exhibit an explicit family of Boolean functions for which (Formula Presented) is (Formula Presented). Going further, we use an affine transform A, such that the corresponding function g satisfies (Formula Presented), to prove that for (Formula Presented), the bounded error quantum communication complexity of F with prior entanglement, (Formula Presented) is (Formula Presented). Our proof builds on ideas from Sherstov [17] where we use specific properties of the above affine transformation. Using this, we show the following. (a)For a fixed prime p and an (Formula Presented), any Boolean function f that depends on all its inputs with (Formula Presented) must satisfy (Formula Presented). Here, (Formula Presented) denotes the degree of the multilinear polynomial over (Formula Presented) which agrees with f on Boolean inputs.(b)For Boolean function f such that there exists primes p and q with (Formula Presented) for (Formula Presented), the deterministic communication complexity - (Formula Presented) and (Formula Presented) are polynomially related. In particular, this holds when (Formula Presented). Thus, for this class of functions, this answers an open question (see [2]) 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, (Formula Presented). Using this new relation, we exhibit Boolean functions f (other than the parity function) such that (Formula Presented) is (Formula Presented) where (Formula Presented) is the number of non-zero coefficients in the Fourier representation of f. © Springer Nature Switzerland AG 2019.