Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR24-070 | 10th April 2024 06:41

Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing


Authors: Xinyu Mao, Guangxu Yang, Jiapeng Zhang
Publication: 10th April 2024 08:13
Downloads: 219


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.

ISSN 1433-8092 | Imprint