| |
|
Title
题目 |
Approximate Counting via Correlation Decay |
|
|
Speaker
报告人 |
Prof. Pinyan Lu |
|
Theory Group, Microsoft Research Asia, Beijing and Department of Computer Science,Tongji University, Shanghai |
|
Date
日期 |
2013-10-14 AM 10:30 Monday |
|
Venue
地点 |
Conference Hall 322, ITP/理论物理所322报告厅 |
|
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. |
|
Contact
所内联系人 |
周海军 |
Bio:
Dr. Pinyan Lu is a Lead Researcher at Theory Group of Microsoft Research Asia. He is also a Chair Professor at 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 focus on complexity and approximability of counting problems, and algorithmic mechanism design. He has received various awards, including the Best Paper Award in ICALP 2007, FAW 2010, ISAAC 2010 and so on.
http://research.microsoft.com/en-us/people/pinyanl/ | 
