Algorithmic Meta-theorems, where Logic Meets Algorithms
- Prof. Yijia Chen，Fudan University
- Time: 2019-06-25 10:00
- Host: Dr. Yuqing Kong
- Venue: Room 102, Courtyard No.5, Jingyuan
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
Professor Yijia Chen, Ph. D. in computer Science, Shanghai Jiaotong University, Ph. D. in Mathematics, University of Freiburg, Germany, is currently a professor in the School of computer Science and Technology, Fudan University. His main research fields are logic, computational complexity and algorithm graph theory, especially parameter complexity and finite model theory. His works are published in first-class computer journals JACM, SICOMP, first-class conferences FOCS, LICS, ICALP, mathematical logic first-class journals JSL, APAL, etc. Professor Yijia Chen has won the Microsoft Young Professor Award, the ICALP'10 International Conference on theoretical computer Science and the WG'17 Best thesis Award from the International Conference on Graph Theory. He has served as a procedural member of the LICS Conference many times.