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.

The first session of this mini course will take place on Monday, August 29th, 2016 11:00 am – 12:00 pm; the second session of this mini course will take place on Tuesday, August 30th, 2016 11:00 am – 12:00 pm; the third session of this mini course will take place on Wednesday, August 31st, 2016 9:30 am – 10:30 am; the fifth session of this mini course will take place on Friday, September 2nd, 2016 11:00 am – 12:00 pm.