Instructor: Neil Immerman

What is this course about? Descriptive Complexity measures the computational complexity of a property via how rich a logical language is needed to express the property. All the main complexity classes have natural descriptive characterizations. To get a taste see this introductory survey of descriptive complexity.

In this seminar we will bring all the participants up to speed concerning descriptive complexity as described in my 1999 book, Descriptive Complexity. We will also delve into more recent developments in descriptive complexity including the work of Ben Rossman and Martin Grohe. 3 credits

Prerequisites: Prerequisite: CS601 or permission of the instructor.

Requirements All students will carefully read the text and papers in advance of their class presentation, and later in the course, each student will present some of the material.

Required text: Neil Immerman, Descriptive Complexity, Springer graduate texts in computer science, 1999.

We will cover much of this book, and read various papers as well.