Dr. Chihao Zhang, The Chinese University of Hong Kong
Mar 20, 2018, Tue, 10:00-11:30
The study of the algorithmic solutions of counting problems has been a central area in theoretical computer science since the birth of the complexity theory. In recent years, an active on-going program is to establish the computational complexity of counting problems under general frameworks. Fruitful results are obtained along this line of research and the complexity of most natural counting problems are well-understood.
However, much less is known about the approximability of counting problems. Approximation, besides being the next question to ask after the understanding of exact counting, has rich connections with other areas like statistical physics and probability theory.
In this talk, I will give an overview of the area with my own research experience in the last five years. I will highlight some central problems and how we managed to attack them.
Chihao Zhang is currently a postdoctoral researcher at the Chinese University of Hong Kong. He obtained his Ph.D. degree from Shanghai Jiao Tong University in 2016. His main research interest lies in the design and analysis of algorithms, especially in approximate algorithms for counting and sampling tasks.