ECCC-Report TR18-152https://eccc.weizmann.ac.il/report/2018/152Comments and Revisions published for TR18-152en-usThu, 30 Aug 2018 14:07:50 +0300
Paper TR18-152
| Sensitivity, Affine Transforms and Quantum Communication Complexity |
Krishnamoorthy Dinesh,
Jayalal Sarma
https://eccc.weizmann.ac.il/report/2018/152In 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 &lt; \epsilon &lt; 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$.
Thu, 30 Aug 2018 14:07:50 +0300https://eccc.weizmann.ac.il/report/2018/152