Let H be a group and D be a distribution on the product group H^m which is uniformly distributed on every pair of coordinates. We show that when H = SL(2,q), the convolution of poly(m) independent copies of D gets close to uniform over H^m. Our result extends to other quasirandom groups as well.
In this talk, I will discuss the proof and its connections to the communication complexity of multiplying k x t elements from a group H in the k-party number-on-forehead (NOF) model. Our result implies that for H = SL(2,q), solving this problem requires (t log H)/C^k bits of communication, matching the state-of-the art lower bounds in the area.
Chin Ho Lee is an Assistant Professor of Computer Science at NC State. Before joining NCSU, he was a postdoc at Harvard University from 2021-2023 and Columbia University from 2019-2021. He received his PhD at Northeastern University and his master's and bachelor's degrees at the Chinese University of Hong Kong. His research interests include theoretical computer science, randomness in computation, pseudornadomness, Boolean functions, and trace reconstruction.
Department of Computer Science