Monthly Archives: 九月 2016

  • -

讲座信息:Approximate Counting via Correlation Decay

Category : 未分类

时间: 14:00-15:30, Sep. 6, 2016
题目: Approximate Counting via Correlation Decay
演讲者: 陆品燕教授,上海财经大学信息学院

Abstract: In this talk, I will survey some recent development of approximate counting algorithms based on correlation decay technique. Unlike the previous major approximate counting approach based on sampling such as Markov Chain Monte Carlo (MCMC), correlation decay based approach can give deterministic fully polynomial-time approximation scheme (FPTAS) for a number of counting problems. The algorithms have applications in statistical physics, machine learning, stochastic optimization and so on.

Short Bio:Dr. Pinyan Lu is a professor and the founding director of Institute for Theoretical Computer Science at Shanghai University of Finance and Economics (ITCS@SUFE). Before joining SUFE, he was a researcher at Microsoft Research. He is also a Chair Professor at Computer Science Department and Zhiyuan College of Shanghai Jiao Tong University. He studied in Tsinghua University (BS (2005) and PhD (2009) both in Computer Science). He is interested in theoretical computer science, including complexity theory, algorithms design and algorithmic game theory. Currently, his research is mainly focused on complexity and approximability of counting problems, and algorithmic mechanism design.