A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity

Pavel Dvořák, Bruno Loff, Suhail Sherif

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 statem…