**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.