Optimal lower bounds for universal relation, samplers, and finding duplicates

Jelani Nelson, Jakub Pachocki, Zhengyu Wang

In the communication problem $\mathbf{UR}$ (universal relation) [KRW95], Alice and Bob respectively receive $x$ and $y$ in $\{0,1{\}}^n$ with the promise that $x\ne y$. The last pla…