School of
Electrical Engineering
and Computer Science

# DD2446 Complexity Theory Autumn 2013

Follow these shortcut links to go directly to news, short overview of course, schedule, lecturer, prerequisites, learning outcomes, examination, course material, or problem set info (with a description of the peer evaluation grading process and a list of the actual psets).

This webpage provides all documentation and information about the course, so there is no separate course memo ("kurs-PM") PDF file.

## News

• The course is over.

## Short Overview of Course

Computers are everywhere today—at work, in our cars, in our living rooms, and in our pockets—and have changed the world beyond our wildest imagination. Yet these marvellous devices are, at the core, amazingly simple and stupid: all they can do is to mechanically shuffle zeros and ones around. What is the true potential of such automated computational devices? And what are the limits of what can be done by mechanical calculations?

Complexity theory gives these deep and fascinating philosophical questions a crisp mathematical meaning. A computational problem is any task that is in principle amenable to being solved by a computer—i.e., it can be solved by mechanical application of mathematical steps. Complexity theory focuses on classifying computational problems according to their inherent difficulty, and on relating those classes of problems to each other. The goal is to understand the power of computers but also—and above all—the limitations of what problems can be solved by them, or more broadly by any type of automated computational process. A problem is regarded as inherently difficult if its solution requires unreasonably large resources regardless of which approach is used to solve it (i.e., no matter which algorithm is employed). Complexity theory formalizes this notion by introducing mathematical models of computation and quantifying the amount of resources needed to solve the problems, such as running time, memory usage, parallelism, communication, et cetera.

This course will give an introduction to computational complexity theory, survey some of the major research results, and present some of the open problems that are the focus of current research. While the intention is to give a fairly broad coverage, there will probably be a slight bias towards areas where the Theory Group at KTH has made significant contributions to the state of the art.

## Schedule

This course was given in period 1 in the autumn of 2013. We had a total of 17 lectures, with 2-3 lectures per week. In accordance with the academic quarter tradition at KTH, 10 am in the schedule below actually means 10:15 am et cetera. See the list of rooms at KTH to locate the different lecture rooms. Room 4523, which is not on this list, is a seminar room on the 5th floor at Lindstedtsvägen 5. Chapter numbers in the course planning below refer to the Arora-Barak textbook.

The general idea behind the course was to first go over (most of) the first 9 chapters in the textbook, getting a fairly good general overview of computational complexity theory, and then spend some time on a selection of more "advanced" topics such as proof complexity, communication complexity, property testing, and hardness of approximation (where the textbook was followed less closely or not at all).

 Weekday Date Time Room # Plan of lectures References Tuesday Sep 3 10-12 D34 1. Intro to complexity theory, course overview, Turing machines, P Chs 0-1, notes Wednesday Sep 4 13-15 E33 2. NP and NP-completeness, Cook-Levin theorem, coNP, EXP, NEXP Ch 2, notes Thursday Sep 5 13-15 Q36 3. Diagonalization, time hierarchy theorems, Ladner's theorem, oracle TMs Ch 3, notes Tuesday Sep 10 10-12 L21 4. Space complexity, PSPACE, NPSPACE, L, NL, Savitch's theorem Ch 4, notes Thursday Sep 12 13-15 Q34 5. Immerman-Szelepcsényi theorem, polynomial hierarchy (PH), alternating TMs Chs 4-5, notes Tuesday Sep 17 10-12 E32 6. Boolean circuits, P/poly, Karp-Lipton theorem, Shannon's lower bound Ch 6, notes Thursday Sep 19 13-15 Q34 7. More circuits: NC, AC, Lower bounds for AC0, Håstad's switching lemma Chs 6,14, notes Tuesday Sep 24 10-12 Q22 8. Randomized computation, BPP, RP, coRP, ZPP, randomized reductions Ch 7, notes Wednesday Sep 25 13-15 L22 9. Interactive proofs, IP, AM, IP=PSPACE (but proof of coNP ⊆ IP) Ch 8, notes Thursday Sep 26 13-15 4523 10. MIP, PCP; crypto: one-way functions, pseudorandomness, zero knowledge Ch 9, notes Tuesday Oct 1 10-12 Q21 11. Proof complexity: basics, resolution lower bound for pigeonhole principle Ch 15, [Hak85], notes Thursday Oct 3 14-16 4523 12. Property testing: basic concepts, linearity testing, Fourier analysis [Gol11], [BCH+96], notes Tuesday Oct 8 10-12 Q22 13. Guest lecture by Per Austrin: PCP theorem, hardness of approximation Ch 11, notes Wednesday Oct 9 13-15 E31 14. Guest lecture by Per Austrin: PCP theorem, hardness of approximation (cont.) Ch 22, [Kho10], notes Thursday Oct 10 13-15 E36 15. Communication complexity: 2-party, multiparty, deterministic, randomized Ch 13, notes Tuesday Oct 15 10-12 Q22 16. Randomized and distributional communication complexity, discrepancy [CG88], notes Thursday Oct 17 13-15 L21 17. Discrepancy bound for inner product; summary of course; wrap-up [CG88], notes

## Lecturer

The lecturer was Jakob Nordström, who was responsible for all aspects of the course.

Per Austrin gave two guest lectures on the PCP theorem and hardness of approximation.

We are using Piazza for teacher-student interaction on the course. Thus, questions should not be e-mailed to the instructor, but instead posted on Piazza (where you can send private notes to the instructor if needed, and also ask questions anonymously).

All course participants should be signed up at Piazza to receive all announcements related to the course (but note that this does not replace the official course registration at KTH).

## Prerequisites

The course is open to anyone, but the main target audience are Master's students in computer science. The course is also suitable for PhD students in mathematics or computer science who have not previously taken a dedicated course on computational complexity theory. You need to have taken DD1352 Algorithms, Data Structures, and Complexity or DD2352 Algorithms and Complexity (or the older version DD2354 Algorithms and Complexity mentioned in the Study Handbook), or corresponding courses at other universities, and should feel comfortable with that material. There are no additional formal prerequisites on top of what is stated in the Study Handbook, but you will need mathematical maturity and a willingness to learn new stuff. The lectures will be given in English.

As of the autumn term 2013, students at KTH CSC should register via the "personal menu" ("personliga menyn" in Swedish), which was previously known as "my pages" ("mina sidor"). This replaces the registration previously done via the `rapp.csc.kth.se` system. You need to register in order for the lecturer to be able to report your results. Many different categories of students take this course, however, and might face different administrative problems. Please make sure that you also get registered as appropriate for your study program.

Although the formal prerequisites are very limited, it should be noted that this is a somewhat demanding course (but hopefully even more fun!).

## Formal Learning Outcomes

After having completed the course, the student should be able to:

• Define and motivate basic concepts in complexity theory and explain how these concepts are related to one another.
• Describe the most important research results in modern complexity theory.
• Use standard tools and techniques in modern complexity theory to prove basic theorems and independently solve problems amenable to these methods.
• Present complexity-theoretic arguments with mathematical stringency orally and in writing.
• For the highest grade: read and understand a research article in complexity theory, and display this understanding by giving an oral presentation of the paper.

## Examination

To pass the course, students will be required to solve and hand in solutions to four problem sets. The scores on the problem sets are what will mainly determine the final grades on the course (except as explained below).

For each each problem set, each student will also have to evaluate the solutions of a fellow student (but not assign grades), who will be randomly chosen by the instructor. This part of the examination will only be pass/fail as discussed in the description of the grading process below.

The grades are determined according to the following principles:

• To pass the course, you need a pass (E) on all problem sets. The score needed for an E or higher grades will be stated on each individual problem set. For each pset, you also need to evaluate the solutions of a fellow student.
• In principle, the final grade will be the arithmetic mean of the grades for all the problem sets (except that there is an extra requirement for A as explained below). That is, think of A-E as {5,4,3,2,1}, sum up, and divide by the number of psets.
• If this mean is not integral, later psets will affect the rounding more than earlier psets. Also, if you have done a good job of evaluating pset solutions by fellow students, this will affect the rounding upwards.
• In order to get an A, you need to (a) obtain an average A or B on the problem sets and (b) read and present a research article in complexity theory (to be determined in consultation with the lecturer). The presentation should show that you have grasped the main contributions of the article but there is no need (or time) to be able to give detailed explanations of all the steps in the proofs.
• It is very possible that there will be some corner cases that this set of rules (or any set of rules of reasonable length), cannot exactly capture. In such cases, we will strive to be generous rather than stingy.

Note that solutions to the problem sets should be handed in strictly by the deadlines. Being able to work towards a deadline and deliver the best possible result within a given time frame (rather than a 100% polished product that arrives too late) is an important skill, and is something that you will have the opportunity to practise during the course. Having said that, exceptional circumstances, such as severe illness, can be accepted as an excuse for late problem set solutions. It should be emphasized, however, that lack of time due to work outside the university or due to many parallel courses is not considered as a legitimate reason for handing in problem set solutions late.

The KTH CSC code of honour applies to all aspects of this course including the problem sets. There are also some additional rules specific to (the problem sets of) this course. These rules are available below on this webpage and are stated on each problem set

## Course Material

### Textbook(s)

We will mostly be following the book

at least for the first half of the course. There is also a set of notes by Johan Håstad used in previous offerings of the course that covers some of the basic material and that might be useful side reading.

While Arora-Barak is the recommended textbook, we comment briefly on some other alternatives below. Another recent textbook on computational complexity theory is

This book will probably have a substantial overlap with the course, but will not cover all of it. Two classic references are
While these latter two books are excellent, their coverage is beginning to get fairly out-of-date in view of the developments in complexity theory during the last two decades. Thus, while they are highly recommended reading, it will probably be hard to follow the course using them.

### Research Articles

During the second half of the course, some lectures will be partly based on research articles. Below follows a list of links to these articles. The intention is that the lectures will cover the material in the papers that we need, so students are not required to read these papers—the references are provided for completeness and for students interested in further reading. However, for students interested in learning more, it should be noted that many of the proofs given in class are actually not those found in the papers, and more recent survey papers of an area are likely to be better reads than the original research articles. Please do not hesitate to contact the instructor if you are interested in specific references for some specific area.

Note that if you are not at KTH, or if you are connected to the KTH network via wireless, then you might not be able to access the PDF files with the articles linked to below. One way around this problem is to search for the titles of the papers in your favourite search engine—this should hopefully help you find free versions of the same papers on the webpages of the authors or similar. Another, often better, solution to this problem (courtesy of Lars Arvestad) is to invoke the KTH library proxy server directly in the address field of the browser. You do this by adding `.focus.lib.kth.se` to the domain of the web address where you found the paper in question, which will work if the KTH library has a subscription (this is usually the case). For instance, if you want to look at `http://www.journal.com/somepaper.html` but this paper is behind a pay-wall, you try to change the URL to `http://www.journal.com.focus.lib.kth.se/somepaper.html`. Supposing that the KTH library is paying for the journal in question, this should take you to the paper via a login page for your KTH account.

## Problem Sets

### General Information

Solutions to the problems sets should be submitted as PDF files by e-mail to `jakobn at kth dot se`. Please use the subject line `Problem set <N>: <your name>` and name the PDF file `PS<N>_<YourName>.pdf` with any national characters converted to standard ASCII (so the solutions to the second problem set by the main lecturer would have the file name `PS2_JakobNordstrom.pdf`, for instance). Solutions should be typeset in some math-aware system (read: LaTeX or such like; MS Word with Equation Editor is borderline but might pass). Please try to be precise and to the point in your solutions and refrain from vague statements. Some of the problems in the problem sets are meant to be quite challenging and you are not necessarily expected to solve all of them.

When you are working on the problem sets, discussions of ideas in groups of two are allowed, but you should always write down your own solution individually and understand all aspects of it fully. You should also acknowledge any collaboration. For each problem set, state at the beginning if you have been collaborating and with whom.

You can (and should) ask the instructor if anything about the problem sets is unclear. Make sure to post private messages to the instructor on Piazza in that case, so that your questions do not accidentally give away unintended information about the problems to the other students. If there is some issue needing clarification regarding some problem, the instructor will make a public post on Piazza.

Some of the problems are "classic" and hence it might be easy to find solutions on the Internet, in textbooks or in research papers. It is not allowed to use such material in any way unless explicitly stated otherwise. Anything said during the lectures on in the lecture notes, or which can be found in chapters of Arora-Barak covered in the course, should be fair game, though, unless you are specifically asked to show something that we claimed without proof in class. It is hard to pin down 100% formal rules on what all this means—when in doubt, ask the lecturer.

The description below is currently not entirely up-to-date, as we are experimenting a bit with different set-ups as the course progresses. In particular, the order of steps 2 and 3 have been reversed. There is also a system of bonus point to encourage active discussions. As always, the most up-to-date information can be found on Piazza.

We will try out a new approach this year which will involved some peer evaluation (and hopefully tons of interaction among the students). All final grading will be done by the instructor, however. Here is how it is intended to work.

#### Step 1: Work on the Problem Set

Students solve the problem set, on their own or collaborating in pairs, and write down their own solutions and submit as a PDF file by e-mail before the deadline. During this phase no discussion of problem set solutions is allowed other than with the collaborating partner (but asking the instructor for clarifications is of course OK).

#### Step 2: Discussion of Solutions

As soon as the instructor gives the green light, discussions on solutions to the problems can start on Piazza. During this phase all students on the course should work together to find solutions (possibly many different ones) to all problems on the problem set. Here a maximum of collaboration is allowed and encouraged. There is no incentive not to collaborate here since nothing that happens after this point can lower the grade of any student. The instructor will not take part too actively in the exchange of comments, but will try to nudge the discussions in the right direction if need be.

#### Step 3: Peer Evaluation

Within a day or two (the exact timing will be discussed with the course participants), the instructor will distribute the solutions randomly to the students as PDF files by e-mail. Each student should print the set of solutions received, evaluate all the solutions, and write down comments. Continued discussions on Piazza are encouraged during this phase.

Here is how the solutions should be evaluated:

• Each problem solved should be marked as "correct", "incorrect", or "unknown".
• For a "correct" solution, the key steps in the solution should be highlighted.
• For an "incorrect" solution, the error(s) in the solution should be pointed out together with an explanation what the mistake is.
• If a solution is truly unintelligible, it can be marked as "unknown" and a comment should be provided explaining where the evaluating student gets lost and why. Note, however, that hard-to-understand solutions can be discussed on Piazza (while giving a suitable amount of details in order to maintain the anonymity of both the student being evaluated and the student evaluating), and so this "unknown" option is expected to be very rare.
• General comments discussing possible strong and weak points with the solution are encouraged—please use the opportunity to provide constructive feed-back to a fellow student.
• At all times, please avoid harsh language and excessive criticism. Be polite and try to find not only negative but also positive aspects of the solutions.
• All comments should be clearly legible. Shorter comments should be provided directly on the print-out. Longer comments can be provided on separate sheets of paper where it is clearly marked which comments pertain to which problem solution and where.

The solutions together with the evaluation comments should be should be put in the lecturer's mailbox on the 4th floor at Osquars backe 2 or handed to the lecturer before beginning of class on the day of the peer evaluation deadline.

Finally, the lecturer will grade all problem set solutions and assign scores, and will at the same time evaluate the evaluations. Each student will receive both the instructor grading comments and the peer evaluation.

The problem set will be regarded as a pass if it reaches the threshold for E as specified in the problem set.

The problem set evaluation will be regarded as a pass if at least 50% of the solutions marked as "correct" or "incorrect" are properly identified as such (with relevant explanations), and if no solution is marked "unknown" unless there is a convincing explanation as to why this solution was not possible to understand. In particular, the lecturer might look at the discussions at Piazza to check if the student has made a good faith effort to get help to figure out what is going on in the solution.

#### Motivation for this Set-up

There are a number of reasons why this approach will be used. It is intended to:

• Increase the coverage of the material, so that all students will work on (essentially) all problems regardless of whether they managed to solve them themselves or not.
• Increase in-depth learning, in that students will have to really understand the problems in order to assess someone else's solutions.
• Encourage students to write clearly and intelligibly, so that the text can be understood by their peers.
• Help students develop the skills to read and understand mathematical arguments as presented by others.
• Increase the amount of feed-back provided to each student, in that more individualized comments will be provided than can possibly be done by a single instructor marking all solutions.
• Help the students internalize the course requirements, in that they will gain a greater understanding of what is an appropriate level of detail in the solutions, what is a suitable level of mathematical rigour in the arguments, what makes solutions easy or hard to read, and how this all affects the grading of the solutions.
As a side effect, this process might also help in the final grading of the problem set solutions by the instructor, although this remains to be seen.

This new approach will be thoroughly evaluated during (and certainly after) the course, and might be modified based on the conclusions from such evaluations. If you have any views or comments already now, feel free to contact the instructor on Piazza or by e-mail.

### List of Problem Sets

• Problem set 1 (last revised September 11, 2013): Deadline Tuesday September 17. Peer evaluation due Thursday September 26 at 13:15.
• Problem set 2 (last revised October 21, 2013): Deadline Friday October 4. Peer evaluation due Tuesday October 15 at 10:15.
• Problem set 3 (last revised October 18, 2013): Deadline Monday October 21. Peer evaluation due Monday November 4 at 14:00.
• Problem set 4 (last revised October 30, 2013): Deadline Friday November 8. Peer evaluation due Monday November 18 at 14:00.