X
Sensitivity, affine transforms and quantum communication complexity
Krishnamoorthy Dinesh
Published in Elsevier BV
2020
Abstract

In this paper, we study the Boolean function parameters sensitivity ($\mathsf{s}$), block sensitivity ($\mathsf{bs}$), and alternation ($\mathsf{alt}$) under specially designed affine transforms and show several applications. For a function $f:{\mathbb{F}}_{2}^{n}\to \left\{-1,1\right\}$, and $A=Mx+b$ for $M\in {\mathbb{F}}_{2}^{n×n}$ and $b\in {\mathbb{F}}_{2}^{n}$, the result of the transformation g is defined as $\forall x\in {\mathbb{F}}_{2}^{n},g\left(x\right)=f\left(Mx+b\right)$.

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 $\mathsf{salt}\left(f\right)$). By a result of Lin and Zhang (2017) [7], it follows that $\mathsf{bs}\left(f\right)\le O\left(\mathsf{salt}{\left(f\right)}^{2}\mathsf{s}\left(f\right)\right)$. Thus, to settle the Sensitivity Conjecture ($\forall \phantom{\rule{0.25em}{0ex}}f,\mathsf{bs}\left(f\right)\le \mathsf{poly}\left(\mathsf{s}\left(f\right)\right)$), it suffices to argue that $\forall \phantom{\rule{0.25em}{0ex}}f,\mathsf{salt}\left(f\right)\le \mathsf{poly}\left(\mathsf{s}\left(f\right)\right)$. However, we exhibit an explicit family of Boolean functions for which $\mathsf{salt}\left(f\right)$ is ${2}^{\mathrm{\Omega }\left(\mathsf{s}\left(f\right)\right)}$.

Going further, we use an affine transform A, such that the corresponding function g satisfies $\mathsf{bs}\left(f,{0}^{n}\right)\le \mathsf{s}\left(g\right)$. We apply this in the setting of quantum communication complexity to prove that for $F\left(x,y\right)\stackrel{\text{def}}{=}f\left(x\wedge y\right)$, the bounded error quantum communication complexity of F with prior entanglement, ⁎${Q}_{1/3}^{⁎}\left(F\right)$ is $\mathrm{\Omega }\left(\sqrt{\mathsf{bs}\left(f,{0}^{n}\right)}\right)$. 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 ${\mathsf{deg}}_{p}\left(f\right)\le \left(1-ϵ\right)\mathrm{log}n$ must satisfy ⁎${Q}_{1/3}^{⁎}\left(F\right)=\mathrm{\Omega }\left(\frac{{n}^{ϵ/2}}{\mathrm{log}n}\right)$. Here, ${\mathsf{deg}}_{p}\left(f\right)$ denotes the degree of the multilinear polynomial over ${\mathbb{F}}_{p}$ which agrees with f on Boolean inputs.

(b)

For Boolean function f such that there exists primes p and q with ${\mathsf{deg}}_{q}\left(f\right)\ge \mathrm{\Omega }\left({\mathsf{deg}}_{p}{\left(f\right)}^{\delta }\right)$ for $\delta >2$, the deterministic communication complexity - $\mathsf{D}\left(F\right)$ and ⁎${Q}_{1/3}^{⁎}\left(F\right)$ are polynomially related. In particular, this holds when ${\mathsf{deg}}_{p}\left(f\right)=O\left(1\right)$. 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, $\mathsf{alt}\left(f\right)\le 2\mathsf{s}\left(g\right)+1$. Using this new relation, we exhibit Boolean functions f (other than the parity function) such that $\mathsf{s}\left(f\right)$ is $\mathrm{\Omega }\left(\sqrt{\mathsf{sparsity}\left(f\right)}\right)$ where $\mathsf{sparsity}\left(f\right)$ 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
Journal Data powered by TypesetTheoretical Computer Science Data powered by TypesetElsevier BV No