Header menu link for other important links
Sensitivity, affine transforms and quantum communication complexity
Published in Elsevier B.V.
Volume: 838
Pages: 68 - 80
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:F2n→{−1,1}, and A=Mx+b for M∈F2n×n and b∈F2n, the result of the transformation g is defined as ∀x∈F2n,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) [7], it follows that bs(f)≤O(salt(f)2s(f)). Thus, to settle the Sensitivity Conjecture (∀f,bs(f)≤poly(s(f))), it suffices to argue that ∀f,salt(f)≤poly(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,0n)≤s(g). We apply this in the setting of quantum communication complexity to prove that for F(x,y)=deff(x∧y), the bounded error quantum communication complexity of F with prior entanglement, Q1/3⁎(F) is Ω(bs(f,0n)). 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 ϵ, 0<ϵ<1, any Boolean function f that depends on all its inputs with degp(f)≤(1−ϵ)log⁡n must satisfy [Formula presented]. Here, degp(f) denotes the degree of the multilinear polynomial over Fp which agrees with f on Boolean inputs. (b) For Boolean function f such that there exists primes p and q with degq(f)≥Ω(degp(f)δ) for δ>2, the deterministic communication complexity - D(F) and Q1/3⁎(F) are polynomially related. In particular, this holds when degp(f)=O(1). 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, alt(f)≤2s(g)+1. Using this new relation, we exhibit Boolean functions f (other than the parity function) such that s(f) is Ω(sparsity(f)) where 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 (2019) [5]). © 2020 Elsevier B.V.
About the journal
JournalData powered by TypesetTheoretical Computer Science
PublisherData powered by TypesetElsevier B.V.