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 listsPost Masters Consultancies Monday 18th August, 2014 Developmental Neurobiology Seminar Series Clare Hall Thursday Lunchtime Talks## Other talksBasque and French: Ethnicity, Culture, and Geography in Basque Political Thought (1780s-1850s) Bradford Hill Seminar with Professor Andrew Morris - Title TBC Using Inclusive Design to Focus on User Experience (UX) Reorientating learning for career relevance: Leadership development and professional identities Growing old yet staying young: do bats hold the secret of extended longevity? Hinkley Point C – a template for the future of nuclear new build |