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 listsCambridge University Geographical Society (CUGS) talks CUCS CU Pakistan Society## Other talksResponsible Research and Innovation Lunch- Lent 2018 Perfect toposes and infinitesimal weak generation Autumn Cactus & Succulent Show Magnetic van der Waals Materials: Potentials and Applications MicroRNAs as circulating biomarkers in cancer Around the world in 605 State energy agreements |