Lifting for Arbitrary Gadgets

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)\ge s\cdot (\frac{\mathrm{\Omega }(D(g))}{\log \mathsf{r}\mathsf{k}(g)}-\log \mathsf{r}\mathsf{k}(g)),$$ where $D(\cdot )$ denotes the deterministic communication complexity and $\mathsf{r}\mathsf{k}(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)=\mathrm{\Omega }(\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 $\mathrm{\Omega }(n\cdot \sqrt{D(g)})$ bits.