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会议程序委员。