题目：Parameterized algorithm and complexity

时 间：2015年5月29日（星期五）10:00-11:00

地 点：6-103教室

主讲人：陈翌佳教授

主办单位：数学与统计学院

内容摘要

Parameterized complexity is a relatively young branch of algorithm and complexity theory. By exploiting some small parameters of problem instances, it provides exponential time algorithms whose super polynomial behavior is confined in those parameters. One typical example is the NP-hard vertex cover problem, and parameterized algorithms solve it in linear time when the size of vertex cover is logarithmic to the size of the input graph.In this talk, I will explain the origin of this theory, its main tools, and some of the recent results.

主讲人简介

复旦大学计算机科学技术学院教授、博士生导师。2004年获得德国弗莱堡大学数学系博士学位；2000年获得上海交通大学计算机软件与理论专业博士学位。2008年获得第二届“微软青年教授奖”；2010年获得ICALP最佳论文奖；2013年获得中创软件基金人才奖。在国际高水平杂志、会议上发表学术论文三十余篇。

2012年在Journal of the ACM （JACM）上，陈翌佳教授与德国弗莱堡大学数学系的Joerg Flum教授合作发表了题为“From almost optimal algorithms to logics for complexity classes via listings and a halting problem”的论文。JACM作为美国计算机协会（Association for Computing Machinery，简称ACM）的旗舰刊物，创刊于1954年。现每年出版6期，每期刊登5篇左右的文章，均为全世界范围内计算机领域最重要的研究结果，特别是强调那些在计算机科学子领域间，以及计算机科学与其它学科间的交叉成果。到目前为止，国内在该刊物上一共发表了三篇论文。