【静园5号院科研#8】Algorithmic Meta-theorems, where Logic Meets Algorithms
时间：2019-06-25 来源：CFCS作者：Yuqing Kong
Time: 2019-06-25 10:00-11:00
Speaker: Professor Yijia Chen，Fudan University
Host: Dr. Yuqing Kong
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.