Header menu link for other important links
Sensitivity, affine transforms and quantum communication complexity
, Krishnamoorthy Dinesh
Published in Elsevier BV

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 MF2n×n and bF2n, the result of the transformation g is defined as xF2n,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(xy), 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.


For a fixed prime p and an ϵ, 0<ϵ<1, any Boolean function f that depends on all its inputs with degp(f)(1ϵ)logn must satisfy ⁎Q1/3(F)=Ω(nϵ/2logn). Here, degp(f) denotes the degree of the multilinear polynomial over Fp which agrees with f on Boolean inputs.


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]).

About the journal
JournalData powered by TypesetTheoretical Computer Science
PublisherData powered by TypesetElsevier BV
Open AccessNo