We put forth gadget-less lifting, a new framework for proving the communication lower bounds, which combines the structure-vs-pseudorandomness decomposition by Göös, Pitassi, and Watson (FOCS 17) with a sampling process for analyzing the accuracy of communication protocols.

To prove communication lower bounds for a two-party function f, gadget-less lifting proceeds in three steps: 

(1) Identify a class of simple protocols that captures the hardness of f.

(2) Prove that every communication protocol for f can be simulated by simple protocols. 

(3) Prove lower bounds by analyzing simple protocols.

As an example, we prove the Ω(n / k + k) lower bound on (k - 1)-round distributional complexity of the k-step pointer chasing problem under the uniform input distribution, improving the Ω(n/k - k\log n) lower bound due to Yehudayoff (Combinatorics Probability and Computing, 2020). Our lower bound matches the (k-1)-round protocol with Õ(n/k + k) communication by Nisan and Wigderson (STOC 91). 

The new framework bypasses some fundamental barriers of the round elimination method and information complexity. It may have more applications in proving round-communication trade-offs for other problems.

Xinyu Mao is currently pursuing a PhD at the University of Southern California. Prior to USC, he graduated from Shanghai Jiao Tong University in 2022 with a Bachelor of Engineering degree.His research focuses on theoretical computer science, especially cryptography and computational complexity.