題目：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篇左右的文章，均為全世界范圍內計算機領域最重要的研究結果，特別是強調那些在計算機科學子領域間，以及計算機科學與其它學科間的交叉成果。到目前為止，國內在該刊物上一共發表了三篇論文。
