Get all the updates for this publication
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) [7], 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) [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 ϵ, , 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.
(b)
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) [15]) 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) [5]).
Journal | Data powered by TypesetTheoretical Computer Science |
---|---|
Publisher | Data powered by TypesetElsevier BV |
Open Access | No |