Math 290D: Participating Seminar on Descriptive Complexity Theory
| Contact: | Anush Tserunyan
|
| Email: | anush at math.ucla.edu
|
| Meeting Time: | T 3:00pm-4:50pm
|
| Location: | MS 6118
|
Course Description
We will mainly use Neil Immerman's Descriptive Complexity book, but we will also go over some important papers in complexity theory.
Lectures:
1. Tuesday, April 7, Anush Tserunyan: Introduction to Descriptive Complexity Theory, Definitions and Notation [Chapters 1 and 2 of Immerman's book].
2. Tuesday, April 14, Anush Tserunyan: Alternation, A Complete Problem for P, Least Fixed Point Operator (LFP), Theorem (Immerman and Vardi): P=FO(LFP) [Chapters 3 and 4 of Immerman's book].
3. Tuesday, April 21, Justin Palumbo: Second Order Logic, Fagin's Theorem: NP = SO-Existential, Spectrum Theorem [Chapter 7 of Immerman's book, also see Fagin's paper].
4. Tuesday, April 28, Yoann Dabrowski: Ehrenfeucht–Fraïssé Games, Non-Definability of Some Relations in FO, Zero-One Laws [Chapter 6 of Immerman's book].
5. Tuesday, May 5, Anush Tserunyan: T. P. Baker, J. Gill, R. Solovay, "Relativizations of the P =? NP Question".
6. Tuesday, May 26, Jennifer Padilla: A. A. Razborov, S. Rudich, "Natural Proofs".
7. Tuesday, June 2, Victoria Noquez: A. Mate, "Nondeterministic Polynomial-Time Computations and Models of Arithmetic".