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

Michael Kapralov, Jelani Nelson, Jakub Pachocki +3

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