Speaker: Yijia Chen Shanghai Jiao Tong University
Time: 2012-01-04 15:30-2012-01-04 16:30
Venue: FIT 1-222
Download: Click!
Abstract:
Although theory of algorithms and complexity has its origin in logic, logic did not play a major role in its development since 80's. However there are some recent results showing that logic can help us to better understand some algorithmic and complexity problems, which at first sight seems not to be related. In this talk, I will explain two of our results in such a direction.
For the first result, I will describe linear time algorithms for finding k-edge induced subgraph. As a major component of our algorithms, we use some algorithmic meta-theorems on first-order logic and graphs with bounded local treewidth.
As the second result, I will show that a logic proposed by Blass and Gurevich captures P if and only if there is a polynomial optimal propositional proof system (for TAUT).
These results are from joint work with Bingkai Lin, and with Joerg Flum, respectively.
Short Bio:
Yijia Chen is a professor of Shanghai Jiaotong University. He got his ph.d. in computer science from the same university, and a second ph.d. in mathematics from University of Freiburg. He had also worked in University of Paris-Sud and Humboldt-University in Berlin as Postdoc. His main research interests are logic in computer science, computational complexity, and algorithmic graph theory.
