Communication Complexity of Collision

Mika Göös, Siddhartha Jain

The Collision problem is to decide whether a given list of numbers $(x_1,\dots ,x_n)\in [n{]}^n$ is $1$-to-$1$ or $2$-to-$1$ when promised one of them is the case. We show an $n^{Ω(1)…