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 Humanist Group - meet up Active Materials Type the title of a new list here## Other talksPTPmesh: Data Center Network Latency Measurements Using PTP History of Migration Law Single Cell Seminars (September) Novel Mechanisms of Dysregulated Endothelium in Pulmonary Arterial Hypertension Lunchtime Talk: Helen's Bedroom Simplicial and cubical sets - how they relate to each other (joint work with Chris Kapulkin) |