## Evaluating Formulas on Sparse Graphs

**Lecturer:**
Prof. Anuj Dawar (University of
Cambridge, UK).

About the lecturer | Course Summary | Slides Part 1 Part 2 Part 3 Part 4 | References | Assignment

**Attention: assignment updated 19-11-2010**

**About the lecturer:**
Anuj Dawar has a Bachelor's degree from the Indian Institute of
Technology, Delhi, a Master's degree from the University of Delaware
and a PhD obtained from the University of Pennsylvania in 1993. He
worked for several years in Swansea before moving to Cambridge in
1999, where he is now Professor of Logic and Algorithms and Deputy
Head of the Computer Laboratory. His research has focussed on
applications of logic in computer science. In particular, finite
model theory and its connection to the study of computational
complexity; the theory of databases; the complexity of games and the
expressive power of logical formalisms.

**Course summary:**
Many algorithmic problems can be cast in the form: given a structure
(such as a finite graph G) check that it has some specified property
f. We are interested in investigating the question of how the
richness of the structure and the complexity of the property together
contribute to the computational complexity of verifying that G
satisfies f. Formally, f is specified as a formula in a logic (such
as first-order logic, or fragments of second-order logic) and we look
at the complexity of the satisfaction relation. Restricting G to be a
graph from a suitably sparse class (such as graphs of bounded degree
or planar graphs) is one way of getting a handle on the complexity of
the problem. We will examine a number of such restrictions and draw
on results from descriptive complexity, graph structure theory and
parameterized complexity to see how the satisfaction relation can be
made tractable. In particular, we will look at the fixed-parameter
tractability of first-order logic and monadic second-order logic on a
number of interesting graph classes.

Slides Part 1,
Part 2,
Part 3,
Part 4

References

Please send the solutions to professor Dawar
(Anuj DOT Dawar AT cl DOT cam DOT ac DOT uk) by
**30 November 2010**.