论文标题
碰撞的沟通复杂性
Communication Complexity of Collision
论文作者
论文摘要
碰撞问题是确定给定的数字列表$（x_1，\ ldots，x_n）\ in [n]^n $是$ 1 $ -to-to- $ 1 $还是$ 2 $ -2 $ -TO-to- $ 1 $。我们向天然的两党碰撞版本的$ n^{ω（1）} $随机通信下限，爱丽丝（Alice）拥有每个$ x_i $的上半部分，而鲍勃（Bob）则保持下半场。作为一个应用程序，我们还显示了一个类似的弱位孔搜索问题的下限，该问题回答了Isykson和Riazanov（CCC 2021）的问题。
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^{Ω(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).
