Complexity Theory (Autumn 2011)

Time and location
Event Time Location
Lectures and
practice sessions
Thu 16:15 - 17:45 Liivi 2-404 Peeter Laud and
Bingsheng Zhang
Fri 14:15 - 15:45 Liivi 2-405

Grades will be based on

As the expected number of students attending the course will not be large, we will try to do the final exam orally.

As a theoretical subject, the course will consist mostly of lectures, although we try to study the contents of various complexity classes with the help of exercises, too. The main book for the course will be Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak. We will additionally make use of the book Computational Complexity by Christos H. Papadimitriou. There are also lecture notes (in Estonian) by Mati Tombak, but we will not follow these too closely.
From the first book, we try to cover at least chapters 1—8, 11, 17, 20. We'll get more details from the second book.

In order to have a record of what we did after the end of the semester, and anticipating that the level of detail in lecture slides will not bee too great, we shall scribe the lectures. For each week or topic, we shall select a student whose task is to take detailed notes in the lecture and write it down later, possibly filling in the gaps that we did not explore in the lecture. We will discuss this further in the first lecture.
When you write down the lecture (presumably in LaTeX), please use this preamble in the way shown here (both files are lifted from here).



Bingsheng keeps the exercise session sheet here. If you seem to be getting the sheet for an old session then either Bingsheng hasn't updated it yet or you should flush your browser cache.

Slides of the lectures will appear here. Most probably, they will not be extensive. We will also use Ahto Buldas's slides from previous years.

Scribe notes: