2017/01/16 by Ryuhei Mori, Mori, Ryuhei
Computer Science · Physics and Astronomy · #Chaos-based Image/Signal Encryption #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #FOS: Physical sciences #Information Theory (cs.IT) #Quantum Mechanics and Applications #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.1701.04327
openalex publication_date 2017/01/16 · openalex created_date 2019/07/30 · openalex updated_date 2026/07/28
Buhrman showed that an efficient communication protocol implies a reliable XOR game protocol. This idea rederives Linial and Shraibman's lower bounds of communication complexity, which was derived by using factorization norms, with worse constant factor in much more intuitive way. In this work, we improve and generalize Buhrman's idea, and obtain a class of lower bounds for classical communication complexity including an exact Linial and Shraibman's lower bound as a special case. In the proof, we explicitly construct a protocol for XOR game from a classical communication protocol by using a concept of nonlocal boxes and Pawłowski et al.'s elegant protocol, which was used for showing the violation of information causality in superquantum theories.