报告题目：Algorithmic meta-theorems, where logic meets algorithms.

  报告摘要：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 some of our recent work on algorithmic meta-theorems for small circuit complexity classes.