Evaluating Formulas on Graphs

Add to your list(s) Download to your calendar using vCal

• Anuj Dawar (University of Cambridge)
• Tuesday 30 November 2010, 13:00-14:00
• Computer Laboratory, William Gates Building, Room SS03.

If you have a question about this talk, please contact Thomas Tuerk.

We consider the computational complexity of the following problem: given a first-order formula f in the language of graphs (i.e. with one binary relation) and a finite graph G, determine whether f is satisfied in G. The complexity is generally exponential in the size of f, though polynomial in the size of G. The problem is quite general and encompasses many known hard decision problems on graphs. I well explain how the problem can be made more tractable on restricted classes of graphs, which will lead us to a brief exploration of graph structure theory.

This talk is part of the Computer Laboratory Automated Reasoning Group Lunches series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory Automated Reasoning Group Lunches
• Computer Laboratory, William Gates Building, Room SS03
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• yk373's list

Note that ex-directory lists are not shown.