[06-12] Classification Program for Counting Problems

文章來源:  |  發布時間:2019-06-06  |  【打印】 【關閉


Title:  Classification Program for Counting Problems  

Speaker: Jin-Yi Cai 

Venue:  Seminar Room (Room 334), Building 5, Institute of Software, CAS 

Time:  10:00, June 12th, Wednesday 2019 


Abstract: Complexity Theory is the study of intrinsic difficulty of computational problems.  One primary goal concerns with the classification of various problems, and P versus NP theory has been the canonical framework.  For counting problems the corresponding framework is P versus Valiant's class #P, which is a quantitative version of NP:  Instead of asking whether a problem instance has a solution (the NP type question), it asks how many solutions it has (the #P type question). Many classical problems from statistical physics can also be formulated in this setting, such as the Ising model, Potts model, hardcore gas model, and monomer dimer model.  These are sum-of-product computations. 

  I will give a survey of the classification program for counting problems. They usually are achieved as dichotomy theorems which classify every problem in a broad class into either polynomial time computable (in P), or #P-hard. The classes of problems include counting  graph homomorphisms, constraint satisfaction problems, and Holant problems. I will report some new progress (unpublished) on the bounded degree case. 


BioJin-Yi Cai studied at Fudan University. He continued his study at Temple University andat Cornell Universitywhere he received his Ph. D. in 1986. He held faculty positions at Yale University1986-1989), Princeton University1989-1993), and SUNY Buffalo1993-2000), rising from Assistant Professor to Full Professor in 1996. He is currently a Professor of Computer Science and Steenbock Professor of Mathematical Sciences at the University of Wisconsin--Madison.   

  He received a Presidential Young Investigator Award in 1990 an Alfred P. Sloan Fellowship in Computer Science in 1994a John Simon Guggenheim Fellowship in 1998 and a Morningside Silver Medal of Mathematics in 2004. He also received the Humboldt Research Award for Senior U.S. Scientists. He has been elected a Fellow of ACM AAAS and a foreign member of Academia Europaea.   

  He is an Editor of Journal of Computer and Systems Sciences (CSS), an Editor of International Journal of Foundations of Computer Sciencean Associate Editor of Journal of Complexityan Editor of The Chicago Journal of Theoretical Computer Scienceand an Area Editor for International Journal of Software and Informatics. He works in computational complexity theory. He has written and published over 100 research papers. 

浙江6十1走势图表 一定牛广东十一选五 11选5任3最佳投注方法 pk10牛牛开奖记录 10分快3最新开奖 黑龙江快乐10分推荐 29选7开奖 微乐长春麻将小鸡飞蛋 李逵劈鱼捕鱼游戏大厅 环岛赛飞鱼 熊猫棋牌手机游戏下载 心悦吉林麻将安卓下载安装 广东快乐10分复式玩法 新疆18选7中奖金额 广东推倒胡麻将技巧 新浪财经股票首页 20040810期快乐扑克开奖号