Get all the updates for this publication

Other

Sensitivity, affine transforms and quantum communication complexityPublished in Elsevier BV

2020

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

Going further, we use an affine transform *A*, such that the corresponding function *g* satisfies $\mathsf{bs}(f,{0}^{n})\le \mathsf{s}(g)$. We apply this in the setting of quantum communication complexity to prove that for $F(x,y)\stackrel{\text{def}}{=}f(x\wedge y)$, the bounded error quantum communication complexity of *F* with prior entanglement, ⁎${Q}_{1/3}^{\u204e}(F)$ is $\mathrm{\Omega}(\sqrt{\mathsf{bs}(f,{0}^{n})})$. 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<\u03f5<1$, any Boolean function *f* that depends on all its inputs with ${\mathsf{deg}}_{p}(f)\le (1-\u03f5)\mathrm{log}n$ must satisfy ⁎${Q}_{1/3}^{\u204e}(F)=\mathrm{\Omega}\left(\frac{{n}^{\u03f5/2}}{\mathrm{log}n}\right)$. Here, ${\mathsf{deg}}_{p}(f)$ 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}(f)\ge \mathrm{\Omega}({\mathsf{deg}}_{p}{(f)}^{\delta})$ for $\delta >2$, the deterministic communication complexity - $\mathsf{D}(F)$ and ⁎${Q}_{1/3}^{\u204e}(F)$ are polynomially related. In particular, this holds when ${\mathsf{deg}}_{p}(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, $\mathsf{alt}(f)\le 2\mathsf{s}(g)+1$. Using this new relation, we exhibit Boolean functions *f* (other than the parity function) such that $\mathsf{s}(f)$ is $\mathrm{\Omega}(\sqrt{\mathsf{sparsity}(f)})$ where $\mathsf{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]).

Postprint Version

Content may be subject to copyright,Check License© This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/by-nc... ...© This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/by-nc-nd/4.0/

About the journal

Journal | Data powered by TypesetTheoretical Computer Science |
---|---|

Publisher | Data powered by TypesetElsevier BV |

Open Access | No |