A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity
<|reference_start|>A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity: We study semidefinite relaxations of $\Pi_1$ combinatorial statements. By relaxing the pigeonhole principle, we obtain a new "quantum" pigeonhole principle which is a stronger statement. By relaxing statements of the form "the communication complexity of $f$ is $> k$", we obtain new communication models, which we call "$\gamma_2$ communication" and "quantum-lab protocols". We prove, via an argument from proof complexity, that any natural model obtained by such a relaxation must solve all Karchmer--Wigderson games efficiently. However, the argument is not constructive, so we work to explicitly construct such protocols in these two models.<|reference_end|>
@article{dvořák2024a,
    title={A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of
  Communication Complexity},
    author={Pavel Dvov{r}'ak, Bruno Loff, Suhail Sherif},
    journal={arXiv preprint arXiv:2409.04592},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.04592},
    primaryClass={cs.CC}
}