The notion of query-to-communication lifting theorems is a generic framework to convert query lower bounds into two-party communication lower bounds. Though this framework is very generic and beautiful, it has some inherent limitations such as it only applies to lifted functions. In order to address this issue, we propose gadgetless lifting, a new framework to prove communication lower bounds. The crux of the new approach is to lift lower bounds for a family of restricted protocols into lower bounds for general protocols.

To demonstrate the power of gadgetless lifting, we prove an $\Omega(n / k + k)$ communication lower bound on $(k - 1)$-round distributional complexity of the $k$-step pointer chasing problem under the uniform input distribution, improving the $\Omega(n/k - k\log n)$ lower bound due to Yehudayoff (Combinatorics Probability and Computing, 2020). Our lower bound almost matches the upper bound of $\widetilde{O}(n/k + k)$ communication by Nisan and Wigderson (STOC 91).

A key step in gadgetless lifting is how to choose the definition of restricted protocols. We start with proving communication lower bounds for restricted protocols, and then lift it into general settings. In this paper, our definition of restricted protocols is inspired by the structure-vs-pseudorandomness decomposition by Göös, Pitassi, and Watson (FOCS 17) and Yang and Zhang (STOC 24).

Previously, round-communication trade-offs were mainly obtained by round elimination and information complexity. However, both methods have some obstacles in some settings. In general, we believe gadgetless lifting provides a new solution to address previous barriers by round elimination and information complexity.