**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.