Random Walk on High Dimensional Expanders (1/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

Aug 23, 2021

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.