Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-152 | 30th August 2018 12:46

Sensitivity, Affine Transforms and Quantum Communication Complexity


Authors: Krishnamoorthy Dinesh, Jayalal Sarma
Publication: 30th August 2018 14:07
Downloads: 360


In this paper, we study the Boolean function parameters sensitivity ($\mathbf{s}$), block sensitivity ($\mathbf{bs}$), and alternation ($\mathbf{alt}$) under specially designed affine transforms and show several applications. For a function $f:\mathbb{F}_2^n \to \{0,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 $\mathbf{salt}(f)$). By a result of Lin and Zhang (2017), it follows that $\mathbf{bs}(f) \le O(\mathbf{salt}(f)^2\mathbf{s}(f))$. Thus, to settle the Sensitivity Conjecture ($\forall~f, \mathbf{bs}(f) \le poly(\mathbf{s}(f))$), it suffices to argue that $\forall~f, \mathbf{salt}(f) \le poly(\mathbf{s}(f))$. However, we exhibit an explicit family of Boolean functions for which $\mathbf{salt}(f)$ is $2^{\Omega(\mathbf{s}(f))}$.

Going further, we use an affine transform $A$, such that the corresponding function $g$ satisfies $\mathbf{bs}(f,0^n) \le \mathbf{s}(g)$, to prove that for $F(x,y) := f(x \land y)$, the bounded error quantum communication complexity of $F$ with prior entanglement, $Q^*_{1/3}(F)$ is $\Omega(\sqrt{\mathbf{bs}(f,0^n)})$. Our proof builds on ideas from Sherstov (2010) where we use specific properties of the above affine transformation. Using this, we show the following.

* For a fixed prime $p$ and an $\epsilon$, $0 < \epsilon < 1$, any Boolean function $f$ that depends on all its inputs with $\mathbf{deg}_p(f) \le (1-\epsilon)\log n$ must satisfy $Q^*_{1/3}(F) = \Omega\left (\frac{n^{\epsilon/2}}{\log n} \right )$. Here, $\mathbf{deg}_p(f)$ denotes the degree of the multilinear polynomial over $\mathbb{F}_p$ which agrees with $f$ on Boolean inputs.

* For Boolean function $f$ such that there exists primes $p$ and $q$ with $\mathbf{deg}_q(f) \ge \Omega(\mathbf{deg}_p(f)^\delta)$ for $\delta > 2$, the deterministic communication complexity - $\mathbf{D}(F)$ and $Q^*_{1/3}(F)$ are polynomially related. In particular, this holds when $\mathbf{deg}_p(f) = O(1)$. Thus, for this class of functions, this answers an open question (see \cite{BW01}) 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, $\mathbf{alt}(f) \le 2\mathbf{s}(g)+1$. Using this new relation, we exhibit Boolean functions $f$ (other than the parity function) such that $\mathbf{s}(f)$ is $\Omega(\sqrt{\mathbf{sparsity}(f)})$ where $\mathbf{sparsity}(f)$ is the number of non-zero coefficients in the Fourier representation of $f$.

ISSN 1433-8092 | Imprint