【静园5号院科研#8】Algorithmic Meta-theorems, where Logic Meets Algorithms
时间:2019-06-25 来源:CFCS作者:Yuqing Kong
Time: 2019-06-25 10:00-11:00
Venue: 北京大学静园五院102
Speaker: Professor Yijia Chen,Fudan University
Host: Dr. Yuqing Kong
Abstract:
Many NP-hard problems can be solved efficiently on tree-like graphs. In fact, these results can be unified by a single theorem, i.e., Courcelle's Theorem. It states that every property definable in monadic second-order logic is decidable in linear time on graphs of bounded tree-width. Theorems of this form are known as algorithmic meta-theorems. The last 20 years have seen many algorithmic-meta theorems which build on deep structural graph theory and finite model theory. In this talk I will explain those results and also our recent line of work on algorithmic meta-theorems for small circuit complexity classes. Central to our results are combinatorial characterizations of certain graph classes that are definable in first-order logic, or equivalently, by circuits of small depth.
Biography:
陈翌佳教授,上海交通大学计算机科学博士、德国弗莱堡大学数学博士,现任复旦大学计算机科学技术学院教授。他的主要研究领域为逻辑、计算复杂性和算法图论,特别是参数复杂性和有限模型论。他的结果发表在计算机一流期刊JACM、SICOMP、一流会议FOCS、LICS、ICALP、数理逻辑一流期刊JSL、APAL等。陈翌佳教授曾获微软青年教授奖,理论计算机国际会议ICALP'10及图论国际会议WG'17最佳论文奖,多次担任LICS会议程序委员。