University of Cambridge > Talks.cam > Logic and Semantics Seminar (Computer Laboratory) > Applications of Finite Model Theory in Graph Isomorphism Testing and Propositional Proof Complexity

Applications of Finite Model Theory in Graph Isomorphism Testing and Propositional Proof Complexity

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

If you have a question about this talk, please contact Dominic Mulligan.

In this talk we present new applications of finite model theory in the areas of graph isomorphism testing and propositional proof complexity.

In the first part, we will discuss that the solvability of systems of linear equations and related linear algebraic properties are definable in a fragment of fixed-point logic with counting that only allows polylogarithmically many iterations of the fixed-point operators. This allows us to separate the descriptive complexity of solving linear equation systems from full fixed-point logic with counting by logical means. We then draw a connection from this work in descriptive complexity theory to graph isomorphism testing and propositional proof complexity.

In the second part, we establish further connections between propositional proof complexity and finite model theory. Specifically, we explain how the power of several propositional proof systems, such as Horn resolution, bounded width resolution, and the polynomial calculus of bounded degree, can be characterised in a precise sense by variants of fixed-point logics that are of fundamental importance in finite model theory.

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2017 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity