Logic, Graphs and Parameterized Complexity

Title: Logic, Graphs and Parameterized Complexity
Speaker: 陈翌佳（上海交通大学BASICS实验室）
Time: 15:30,Friday，November 27th
Venue: Lecture Room 334,State Key Lab of Computer Science, Level 3 Building #5, Institute of Software, CAS

Abstract: Parameterized complexity provides a framework for refined analysis of those two-dimensional problems whose one part of the input is relatively small. For example, in the model-checking problems, the length of the specifications is typically far smaller than the size of hardware or software systems; and in the clique problem, the size of the clique we are looking for is often much smaller than the size of the give graph.

In this talk, I will explain two of our recent results to show some occasions in which parameterized complexity gives a satisfying picture of the complexity of certain problems,while classical complexity might not.

In the first result, we show that the problem of deciding whether a first-order logic sentence has a proof of large length is hard, although not necessarily NP-hard. For the second result, we give a complete complexity classification of induced subgraph problems, and prove that essentially it has to be in terms of parameterized complexity instead of the classical complexity.

These results are from joint work with Joerg Flum, and with Marc Thurley and Mark Weyer, respectively.

Biography：
Yijia Chen is an associate 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, France Telecom R&D, and Humboldt-University in Berlin as PostDoc. His main research interests are logic in computer science,computational complexity, and graph theory.