Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-152 | 12th September 2020 06:00

Sensitivity, Affine Transforms and Quantum Communication Complexity

RSS-Feed




Revision #1
Authors: Krishnamoorthy Dinesh, Jayalal Sarma
Accepted on: 12th September 2020 06:00
Downloads: 392
Keywords: 


Abstract:

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 [ICALP 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 [Quantum Information and Computation, 10:435–455, 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 Buhrman and de Wolf [CCC 2001]) 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$. 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, Annals of Mathematics, 190(3): 949-955, 2019].



Changes to previous version:

Added a new lower bound for shifted alternation (in Section 3) and an application to the existence of family of functions under linear transforms (in Section 5).


Paper:

TR18-152 | 30th August 2018 12:46

Sensitivity, Affine Transforms and Quantum Communication Complexity





TR18-152
Authors: Krishnamoorthy Dinesh, Jayalal Sarma
Publication: 30th August 2018 14:07
Downloads: 881
Keywords: 


Abstract:

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