COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

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 ComplexityAdd to your list(s) Download to your calendar using vCal - Wied Pakusa, University of Oxford
- Friday 16 June 2017, 14:00-15:00
- FW26.
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. ## This talk is included in these lists:- All Talks (aka the CURE list)
- Computer Laboratory talks
- Computing and Mathematics
- FW26
- Logic and Semantics Seminar (Computer Laboratory)
- School of Technology
Note that ex-directory lists are not shown. |
## Other listsProteomics as a tool in data driven systems biology language sciences Open Cambridge talks## Other talksTouch: The sensory scaffold of development? The Partition of India and Migration Katie Field - Title to be confirmed Can you handle the truth? Facts, figures and communicating uncertainty Cambridge Judge Experience Day: Entrepreneurship session Exact Gravitational Wave Signatures from Colliding Extreme Black Holes |