Finite and Algorithmic Model Theory

Lecture 1: Finite and Algorithmic Model Theory I
Lecture 2: Finite and Algorithmic Model Theory II
Lecture 3: Finite and Algorithmic Model Theory III
Lecture 4: Finite and Algorithmic Model Theory IV
Lecture 5: Finite and Algorithmic Model Theory V

This series of talks is part of the Logical Structures in Computation Boot Camp. Videos for each talk area will be available through the links above.

Speaker: Anuj Dawar (University of Cambridge)

The aim of this course is to present an overview of concepts, methods and results in several different topics in finite and algorithmic model theory.

Lecture 1: Definability and Undefinability
Introduction to finite model theory. Methods of proving inexpressibility of classes of finite structures. Ehrenfeucht-Fraı̈ssé games. Pebble Games. Locality Theorems. Decomposition theorems.

Lecture 2: Automata-based Methods
Monadic second-order logic (MSO) on finite words and trees.  MSO on infinite words and trees. Finite graphs of bounded tree-width.  Courcelle's theorem.

Lecture 3: Parameterized Model-Checking
The complexity of formula evaluation. Parameterizations by formula size and graph structure. The method of locality: first-order logic on sparse graph classes.

Lecture 4: Descriptive Complexity
Fagin and Immerman-Vardi theorems. The quest for a logic for P.  Counting logics and the Cai-Fürer-Immerman construction. Restricted classes of structures. Linear algebraic problems and rank logics.

Lecture 5: Logic and Combinatorial Optimization
The role of linear programming relaxations. Graph Isomorphism and lift-and-project hierarchies. Definability through the ellipsoid method. Constraint satisfaction problems.