The quantum communication complexity of the pointer chasing problem: The bit version

DOI10.1007/3-540-36206-1_20MaRDI QIDQ4415257zbMATH OpenFDO

Authors Rahul Jain, Pranab Sen, Jaikumar Radhakrishnan

Publication date 28 July 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2556/25560218.htm

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Quantum computation (81P68) Communication networks in operations research (90B18) Measures of information, entropy (94A17)

Recommendations

• Interaction in Quantum Communication
• Interaction in quantum communication and the complexity of \textsc{Set Disjointness}
• The communication complexity of pointer chasing
• Exponential separation of quantum and classical communication complexity
• The communication complexity of pointer chasing: applications of entropy and sampling

Cited in

(13)

• New strong direct product results in communication complexity
• A direct product theorem for two-party bounded-round public-coin communication complexity
• Pointer Quantum PCPs and Multi-Prover Games
• scientific article; zbMATH DE number 2086394 (Why is no real title available?)
• Pointer chasing via triangular discrimination
• Lower bounds and hierarchies for quantum memoryless communication protocols and quantum ordered binary decision diagrams with repeated test
• Interaction in quantum communication and the complexity of \textsc{Set Disjointness}
• Round elimination in exact communication complexity
• scientific article; zbMATH DE number 7650118 (Why is no real title available?)
• The communication complexity of pointer chasing
• The communication complexity of pointer chasing: applications of entropy and sampling
• A direct product theorem for quantum communication complexity with applications to device-independent cryptography
• Pointer chasing with unlimited interaction

This page was built for publication: The quantum communication complexity of the pointer chasing problem: The bit version

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