Video file
Random Walk on High Dimensional Expanders (3/3)
Presenter(s)
Siu On Chan
The Chinese University of Hong Kong
2021 Croucher Summer Course in Information Theory, The Chinese University of Hong Kong
Lecture
Date
Abstract
High dimensional expanders are certain generalizations of expander graphs to hypergraphs. They recently appeared in many randomized algorithms and combinatorial constructions in theoretical computer science. A few random sampling algorithms can be seen as random walks on high dimensional expanders, such as nearly uniformly sampling of spanning trees by exchanging edges. High dimensional expanders also appear in locally testable codes and probabilistically checkable proofs. In this talk, I will give a gentle introduction to high dimensional expanders and survey their recent results.
Biography
Siu On Chan is an Assistant Professor in the CSE Department at the Chinese University of Hong Kong (CUHK). Before joining CUHK, he was a postdoc researcher at Microsoft Research New England. Before that, he obtained his Ph.D. in theoretical computer science at UC Berkeley. His advisors were Luca Trevisan and Elchanan Mossel. Earlier, he obtained his masters at the University of Toronto, under Michael Molloy, and his undergraduate degree at CUHK, working with Leizhen Cai. He is interested in understanding the limitations of approximation algorithms, especially convex optimization algorithms. He is also interested in random graphs, testing and learning.Additional links
Related Videos
