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
- 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.
- 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: