A lifting theorem says: for a suitable two-party gadget $g$ on $O(\log n)$ bits, $$\mathrm{M}^{\mathrm{cc}}(f\circ g^n) \;=\; \Theta\big(\mathrm{M}(f)\cdot \log n\big)$$ for the appropriate pair of query and communication measures $\mathrm{M}$. Known for deterministic [GPW18], randomized, and several LP-based measures.
Consequences visible in this zoo:
- The $\mathrm{D}$-vs-$\mathrm{SP}$ separation [GPW18] was found in order to refute the log-approximate-rank / partition-number conjecture in communication complexity.
- [BenDavidKothari18] note that a zero-error lifting theorem would imply a bounded-error one, via sabotage complexity.
- The strong direct sum of [BlaisBrody19] lifts to $\mathrm{R}^{\mathrm{cc}}(f^k)=\Theta(k\log k\cdot \mathrm{R}^{\mathrm{cc}}(f))$.
- The $\mathrm{D}^{\oplus}$-vs-Fourier-sparsity question is the query analogue of the log-rank conjecture; see Parity decision trees vs Fourier sparsity (query log-rank).