2 papers
cs.CC2025
Key-agreement exists if and only if the "interactive vs non interactive Kolmogorov problem" is not in ioBPP: a short proof
Bruno Bauwens, Bruno Loff
Ball, Liu, Mazor and Pass proved that the existence of key-agreement protocols is equivalent to the hardness of a certain problem about interactive Kolmogorov complexity. We genera…
cs.CC2024
A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity
Pavel DvoÅák, Bruno Loff, Suhail Sherif
We study semidefinite relaxations of combinatorial statements. By relaxing the pigeonhole principle, we obtain a new "quantum" pigeonhole principle which is a stronger state…