Home

Approximation Algorithms for Counting Problems


Speaker

Dr. Chihao Zhang, The Chinese University of Hong Kong

Time

2018-05-20 10:00:00 ~ 2018-05-20 11:30:00

Location

SEIEE-3-412

Host

Huan Long

Abstract
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
Bio
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. http://chihaozhang.com/
© John Hopcroft Center for Computer Science, Shanghai Jiao Tong University
分享到

地址:上海市东川路800号上海交通大学软件大楼专家楼
邮箱:jhc@sjtu.edu.cn 电话:021-54740299
邮编:200240