Evaluating Formulas on Sparse Graphs
Prof. Anuj Dawar (University of
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.
Please send the solutions to professor Dawar (Anuj DOT Dawar AT cl DOT cam DOT ac DOT uk) by 30 November 2010.