2026-07-20T11:27:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22703 2026-04-17T05:32:31Z ddc:004 open_access

Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing Mao, Xinyu Yang, Guangxu Zhang, Jiapeng communication complexity lifting theorems pointer chasing We prove an Ω(n / k + k) communication lower bound on (k - 1)-round distributional complexity of the k-step pointer chasing problem under uniform input distribution, improving the Ω(n/k - klog n) lower bound due to Yehudayoff (Combinatorics Probability and Computing, 2020). Our lower bound almost matches the upper bound of Õ(n/k + k) communication by Nisan and Wigderson (STOC 91). As part of our approach, we put forth gadgetless lifting, a new framework that lifts lower bounds for a family of restricted protocols into lower bounds for general protocols. A key step in gadgetless lifting is choosing the appropriate definition of restricted protocols. 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. Both methods have some barriers in some situations, and we believe gadgetless lifting could potentially address these barriers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xinyu Mao and Guangxu Yang and Jiapeng Zhang 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.75 urn:nbn:de:0030-drops-227038 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.75 eng https://creativecommons.org/licenses/by/4.0/legalcode