# 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

• the final exam (50%);
• some homework for certain topics (20%);
• the produced lecture scripts (see below) (30%).
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).

Homework

• Find the flaw in this paper. Deadline: November 15th. (5 points)
• For any language C define the language VC={1n | the number of elements in C with length n is odd}. Show that there exists a language C, such that VC does not belong to the class NPC. What does that result say about the usefulness of diagonalization arguments to separate NP and PSPACE? Deadline: December 1st. (5 points)
• In the lecture we saw that every function f from {0,1}n to {0,1} can be expressed using O(n⋅2n) gates of bounded fan-in. Based on the equality
f(x1,...,xn)=(xn AND f(x1,...,xn-1,1)) OR ((NOT xn) AND f(x1,...,xn-1,0))
show that each function f can be expressed using O(2n) gates. Deadline: December 15th. (2 points)
• Actually, each function f from {0,1}n to {0,1} can be expressed using O(2n/n) gates of bounded fan-in (see e.g. this, Chap. 2.13). Use this fact to give a tighter circuit size hierarchy theorem. Deadline: December 15th. (3 points)
• Similarly to the class BPP, we could define BPPSPACE. Do it and show that it equals PSPACE. Deadline: December 15th. (2 points)
• Show that if the problem of finding the longest simple path in a directed graph is in the complexity class APX, then it is also in the class PTAS. Deadline: January 2nd. (3 points)

News

• Happy new year! I changed the last homework exercise because the previous one was too complex. Sorry for that.
• The last lectures will be on December 8th and 9th. During the last week of lectures, there will be practice sessions.
• There will be no class meetings on Oct 27th and 28th because of NordSec.
• There was no class meeting on Oct 7th because of the Estonian CS Theory Days.

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: