Collision problems are important problems in complexity theory and cryptography with diverse applications. Previous fruitful works have mainly focused on query models. Driven by various applications, several works independently proposed the communication version of collision problems.

We prove an $\Omega(N^{1/4})$ randomized communication lower bound of the collision problems. Previously, only an $\Omega(N^{1/12})$ was known by a work of Göös and Jain (RANDOM 2022). Our lower bound is tight to some log factors and provides direct applications to cryptography and proof complexity via connections by Bauer, Farshim, and Mazaheri (CRYPTO 2018) and Itsykson and Riazanov (CCC 2021). Our proof is built on a structure-vs-pseudorandomness decomposition inspired by Göös, Pitassi and Watson (FOCS 17), and this technique could be of independent interest.

This is based on joint work with Jiapeng Zhang.

Guangxu Yang is a second-year Ph.D. student advised by Prof. Jiapeng Zhang at the University of Southern California. Previously, He received Bachelor's Degree and M.Sc. Degree in Electrical Engineering from the University of Electronic Science and Technology of China. His research interests lie in communication complexity and combinatorics.