Abstract

The structure-vs-pseudorandomness approach has been remarkably successful in combinatorics; it underlies many landmark results such as Szemerédi’s regularity lemma and the Green–Tao theorem.

In this talk, we bring this powerful methodology to communication complexity, developing a structure-vs-pseudorandomness approach for proving communication lower bounds. Using this approach, we establish a tight randomized communication lower bound for the collision problem, resolving open problems posed by Göös and Jain (RANDOM 2022) and Farshim and Mazaheri (CRYPTO 2018). Our bound has direct implications for cryptography and proof complexity.  We further prove an lower bound on the (k-1)-round distributional communication complexity of the k-step pointer chasing problem under the uniform input distribution, improving upon the previous bound due to Yehudayoff (Combinatorics, Probability and Computing, 2020).

This is based on joint work with Jiapeng Zhang and Xinyu Mao.

Time

Wednesday, Oct. 15, 14:00--15:00

Speaker

Guangxu Yang is a fourth-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.

Room

Room 602