References & Citations
Computer Science > Computational Complexity
Title: Communication Complexity of Collision
(Submitted on 29 Jul 2022 (v1), last revised 9 Aug 2022 (this version, v2))
Abstract: The 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).
Submission history
From: Siddhartha Jain [view email][v1] Fri, 29 Jul 2022 18:20:03 GMT (43kb,D)
[v2] Tue, 9 Aug 2022 21:16:42 GMT (1103kb,D)
Link back to: arXiv, form interface, contact.