Pointer chasing with unlimited interaction

DOI10.1016/J.TCS.2026.116134MaRDI QIDQ7319279zbMATH OpenFDO

Authors Orr Fischer, Rotem Oshman, Adi Rosén

Publication date 25 August 2026

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2026.116134

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A tight bound for set disjointness in the message-passing model
• A tight unconditional lower bound on distributed randomwalk computation
• Communication Complexity
• Communication complexity
• Communication Complexity
• Gadgetless lifting beats round elimination: improved lower bounds for pointer chasing
• Graph Distances in the Data-Stream Model
• scientific article; zbMATH DE number 5764856 (Why is no real title available?)
• scientific article; zbMATH DE number 1954386 (Why is no real title available?)
• scientific article; zbMATH DE number 6146451 (Why is no real title available?)
• scientific article; zbMATH DE number 6767551 (Why is no real title available?)
• Interaction in quantum communication and the complexity of \textsc{Set Disjointness}
• Lower bounds for number-in-hand multiparty communication complexity, made easy
• Lower bounds for predecessor searching in the cell probe model
• NOF-Multiparty Information Complexity Bounds for Pointer Jumping
• On data structures and asymmetric communication complexity
• On quantum and probabilistic communication: Las Vegas and one-way protocols
• On the ``log rank-conjecture in communication complexity
• One-way multiparty communication lower bound for pointer jumping with applications
• Optimal collapsing protocol for multiparty pointer jumping
• Pointer chasing via triangular discrimination
• Polynomial pass lower bounds for graph streaming algorithms
• Privacy and interaction in quantum communication complexity and a theorem about the relative entropy of quantum states
• Private vs. common random bits in communication complexity
• Rounds in Communication Complexity Revisited
• Some bounds on multiparty communication complexity of pointer jumping
• The communication complexity of pointer chasing: applications of entropy and sampling
• Unifying the landscape of cell-probe lower bounds

This page was built for publication: Pointer chasing with unlimited interaction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7319279)