Lifting for Arbitrary Gadgets

Siddharth Iyer

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…