School of
Electrical Engineering
and Computer Science

# DD2445/FDD3445 Complexity Theory Autumn 2017

Follow these shortcut links to go directly to course news, short overview of course, schedule, course material, and list of problem sets.

Go to the separate administrative information page to find information about instructors, prerequisites, learning outcomes, examination, and problem sets in general (with a description of the grading and peer evaluation process).

These webpages provide all documentation and information about the course, so there is no separate course memo ("kurs-PM") PDF file.

## Course 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 and Course Contents

This course was given in periods 1-2 in the autumn of 2017. It had a total of 23 lectures, with 2 lectures per week on average.

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, which are mostly the seminar rooms on the 5th floor at Lindstedtsvägen 3/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, where the textbook was followed less closely or not at all.

 Weekday Date Time Room # Plan of lectures References Tuesday Sep 5 13-15 1537 1. Intro to complexity theory, course overview, Turing machines, undecidability Chs 0-1, notes Friday Sep 8 10-12 4523 2. Complexity classes, reductions, P, NP, nondeterministic computation Chs 1-2, notes Tuesday Sep 12 13-15 1537 3. NP-completeness, Cook-Levin theorem, decision vs. search, coNP, EXP, NEXP Ch 2, notes Friday Sep 15 10-12 1537 4. Diagonalization, time hierarchy theorems, Ladner's theorem Ch 3, notes Tuesday Sep 19 13-15 1537 5. Sagnik Mukhopadhyay: Oracle TMs, space complexity, PSPACE, L, NL Chs 3-4, notes Friday Sep 22 10-12 1537 6. Sagnik Mukhopadhyay: Savitch's theorem, Immerman-Szelepcsényi theorem Ch 4, notes Tuesday Sep 26 13-15 1537 7. Immerman-Szelepcsényi theorem (cont.), polynomial hierarchy (PH) Chs 4-5, notes Friday Sep 29 10-12 1537 8. Polynomial hierarchy (cont.), Boolean circuits, P/poly Chs 5-6, notes Tuesday Oct 3 13-15 1537 9. Sagnik Mukhopadhyay: Karp-Lipton theorem, Meyer's theorem, Shannon's lower bound Ch 6, notes Friday Oct 6 10-12 1537 10. NC, AC, parallel algorithms, P-completeness; randomized computation, BPP Chs 6-7, notes Tuesday Oct 10 13-15 1537 11. Polynomial identity testing, RP, coRP, ZPP, randomized reductions Ch 7, notes Tuesday Oct 31 13-15 1537 12. Sagnik Mukhopadhyay: Communication complexity I [CKLM17], [GPW15], notes Friday Nov 3 10-12 1537 13. Sagnik Mukhopadhyay: Communication complexity II [CKLM17], [GPW15], notes Tuesday Nov 7 14-16 1537 14. Interactive proofs, IP, AM, IP=PSPACE (but proof of coNP ⊆ IP) Ch 8, notes Friday Nov 10 10-12 1537 15. coNP ⊆ IP (cont.), MIP, PCP; crypto: perfect secrecy, one-way functions Chs 8-9, notes Tuesday Nov 14 13-15 1537 16. More crypto: pseudorandomness, zero knowledge Ch 9, notes Friday Nov 17 10-12 1537 17. Bounded-depth circuits, PARITY∉AC0, Håstad switching lemma Ch 14, notes Tuesday Nov 21 13-15 1537 18. Switching lemma (cont.); ACC0, PARITY∉ACC0(3), method of approximations Ch 14, notes Friday Nov 24 10-12 1537 19. Method of approximations (cont.); monotone circuits, clique lower bound Ch 14, notes Tuesday Nov 28 13-15 1537 20. Clique lower bound for monotone circuits (cont.), circuit complexity wrap-up Ch 14, notes Friday Dec 1 10-12 1537 21. Proof complexity, resolution, interpolation, clique-colouring [Pud97], notes Tuesday Dec 5 13-15 1537 22. Clique-colouring lower bound (cont.); clique lower bound for regular resolution [Pud97], [ABdR+17], notes Friday Dec 8 10-12 1537 23. Clique lower bound for regular resolution (cont.); course wrap-up [ABdR+17], notes

## Course Material

### Textbook(s)

We will mostly be following the book

at least for the first half of the course.

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.

### List of Problem Sets

• Problem set 1 (last updated on October 1, 2017): Deadline Friday October 6. Peer evaluation due Monday October 16 at 12 noon.
• Problem set 2 (last updated on November 1, 2017): Deadline Friday November 10. Peer evaluation due Friday November 17 at 10:15.
• Problem set 3 (last updated on November 26, 2017): Deadline Friday December 1. Peer evaluation due Friday December 22 at 12 noon.
• Problem set 4 (last updated on December 23, 2017): Deadline Monday January 22. Peer evaluation due Wednesday January 31 at 12 noon.