ECCC-Report TR22-096https://eccc.weizmann.ac.il/report/2022/096Comments and Revisions published for TR22-096en-usFri, 08 Jul 2022 23:29:33 +0300
Paper TR22-096
| Communication Complexity of Collision |
Mika Göös,
Siddhartha Jain
https://eccc.weizmann.ac.il/report/2022/096The Collision problem is to decide whether a given list of numbers $(x_1,\ldots,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^{\Omega(1)}$ randomised communication lower bound for the natural two-party version of Collision where Alice holds the first half of the bits of each $x_i$ and Bob holds the second half. As an application, we also show a similar lower bound for a weak bit-pigeonhole search problem, which answers a question of Itsykson and Riazanov (CCC 2021).Fri, 08 Jul 2022 23:29:33 +0300https://eccc.weizmann.ac.il/report/2022/096