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

- the final exam (50%);
- some homework for certain topics (20%);
- the produced lecture scripts (see below) (30%).

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*V*={1_{C}^{n}| the number of elements in*C*with length*n*is odd}. Show that there exists a language*C*, such that*V*does not belong to the class_{C}**NP**^{C}. 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*⋅2^{n}) gates of bounded fan-in. Based on the equality

*f*(*x*,...,_{1}*x*)=(_{n}*x*AND_{n}*f*(*x*,...,_{1}*x*,1)) OR ((NOT_{n-1}*x*) AND_{n}*f*(*x*,...,_{1}*x*,0))_{n-1}

show that each function*f*can be expressed using*O*(2^{n}) gates. Deadline: December 15th. (2 points) - Actually, each function
*f*from {0,1}^{n}to {0,1} can be expressed using*O*(2^{n}/*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.

- September 1st
- September 8th
- In September 15th, we'll do the proofs we skipped during the last two lectures. We still did not finish with the proof that SAT is NP-complete, this will be done in the practice session in September 16th. But here are some pictures of the blackboard at the end of the lecture.
- September 22nd
- September 29th and 30th
- On October 6th, we had a practice session. On October 7th, there was no class meeting.
- On October 13th, we continue with the space complexity.
- On October 20th, we will discuss the polynomial hierarchy.
- On November 4th, we talk about circuit complexity.
- We continue with the same (actually, with P-completeness) on November 10th. The slides have been extended.
- On November 17th, we discuss probabilistic computation.
- On November 24th, the topic is interactive proofs.
- We continue on December 8th (the slides have been updated a bit).
- Finally, on December 9th, we talk about counting and approximations.

Scribe notes:

- September 1st (scribe: Alisa Pankova)
- September 8th (scribe: Alisa Pankova)
- September 15th (scribe: Ilja Kuzovkin)
- September 22nd (scribe: Ilja Kuzovkin)
- September 29th and 30th (scribe: Alisa Pankova)
- October 13th and 14th (scribe: Riivo Talviste)
- October 20th and 21st (scribe: Riivo Talviste)
- November 3rd (scribe: Kristjan Krips)
- November 10th (scribe: Kristjan Krips)
- December 8th (scribe: Ilja Kuzovkin)
- December 9th (scribes: Alisa Pankova, Ilja Kuzovkin)