Lifting for Arbitrary Gadgets

Abstract

We prove a sensitivity-to-communication lifting theorem for arbitrary gadgets. Given functions $f:\{0,1{\}}^n\to \{0,1\}$ and $g:\mathcal{X}\times \mathcal{Y}\to \{0,1\}$, denote $f\circ g(x,y):=f(g(x_1,y_1),\dots ,g(x_n,y_n))$. We show that for any $f$ with sensitivity $s$ and any $g$, \[D(f\circ g) \geq s\cdot \bigg(\frac{Ω(D(g))}{\log\mathsf{rk}(g)} - \log\mathsf{rk}(g)\bigg),\] where $D(\cdot )$ denotes the deterministic communication complexity and $\mathsf{rk}(g)$ is the rank of the matrix associated with $g$. As a corollary, we get that if $D(g)$ is a sufficiently large constant, $D(f\circ g)=\hat{I}\text{c◯}(\min \{s,d\}\cdot \sqrt{D(g)})$, where $s$ and $d$ denote the sensitivity and degree of $f$. In particular, computing the OR of $n$ copies of $g$ requires $\hat{I}\text{c◯}(n\cdot \sqrt{D(g)})$ bits.