DD2445 Autumn 2017

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 ("kursPM") PDF
file.

The course is over.

There is a course evaluation that we would like you to fill
in—please see the information sent out on Piazza.

Student paper presentations will hopefully happen in March or
early April and will be announced on Piazza.
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.
This course
was given in periods 12 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
AroraBarak 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 
1315 
1537 
1. 
Intro to complexity theory, course overview, Turing machines, undecidability 
Chs 01, notes 
Friday 
Sep 8 
1012 
4523 
2. 
Complexity classes, reductions, P, NP, nondeterministic computation 
Chs 12, notes 
Tuesday 
Sep 12 
1315 
1537 
3. 
NPcompleteness, CookLevin theorem, decision vs. search, coNP, EXP, NEXP 
Ch 2, notes 
Friday 
Sep 15 
1012 
1537 
4. 
Diagonalization, time hierarchy theorems, Ladner's theorem 
Ch 3, notes 
Tuesday 
Sep 19 
1315 
1537 
5. 
Sagnik Mukhopadhyay: Oracle TMs, space complexity, PSPACE, L, NL 
Chs 34, notes 
Friday 
Sep 22 
1012 
1537 
6. 
Sagnik Mukhopadhyay: Savitch's theorem, ImmermanSzelepcsényi theorem 
Ch 4, notes 
Tuesday 
Sep 26 
1315 
1537 
7. 
ImmermanSzelepcsényi theorem (cont.), polynomial hierarchy (PH) 
Chs 45, notes 
Friday 
Sep 29 
1012 
1537 
8. 
Polynomial hierarchy (cont.), Boolean circuits, P/poly 
Chs 56, notes 
Tuesday 
Oct 3 
1315 
1537 
9. 
Sagnik Mukhopadhyay: KarpLipton theorem, Meyer's theorem, Shannon's lower bound 
Ch 6, notes 
Friday 
Oct 6 
1012 
1537 
10. 
NC, AC, parallel algorithms, Pcompleteness; randomized computation, BPP 
Chs 67, notes 
Tuesday 
Oct 10 
1315 
1537 
11. 
Polynomial identity testing, RP, coRP, ZPP, randomized reductions 
Ch 7, notes 
Tuesday 
Oct 31 
1315 
1537 
12. 
Sagnik Mukhopadhyay: Communication complexity I 
[CKLM17], [GPW15], notes 
Friday 
Nov 3 
1012 
1537 
13. 
Sagnik Mukhopadhyay: Communication complexity II 
[CKLM17], [GPW15], notes 
Tuesday 
Nov 7 
1416 
1537 
14. 
Interactive proofs, IP, AM, IP=PSPACE (but proof of coNP ⊆ IP) 
Ch 8, notes 
Friday 
Nov 10 
1012 
1537 
15. 
coNP ⊆ IP (cont.), MIP, PCP; crypto: perfect secrecy, oneway functions 
Chs 89, notes 
Tuesday 
Nov 14 
1315 
1537 
16. 
More crypto: pseudorandomness, zero knowledge 
Ch 9, notes 
Friday 
Nov 17 
1012 
1537 
17. 
Boundeddepth circuits, PARITY∉AC^{0}, Håstad switching lemma 
Ch 14, notes 
Tuesday 
Nov 21 
1315 
1537 
18. 
Switching lemma (cont.); ACC^{0}, PARITY∉ACC^{0}(3), method of approximations 
Ch 14, notes 
Friday 
Nov 24 
1012 
1537 
19. 
Method of approximations (cont.); monotone circuits, clique lower bound 
Ch 14, notes 
Tuesday 
Nov 28 
1315 
1537 
20. 
Clique lower bound for monotone circuits (cont.), circuit complexity wrapup 
Ch 14, notes 
Friday 
Dec 1 
1012 
1537 
21. 
Proof complexity, resolution, interpolation, cliquecolouring 
[Pud97], notes 
Tuesday 
Dec 5 
1315 
1537 
22. 
Cliquecolouring lower bound (cont.); clique lower bound for regular resolution 
[Pud97], [ABdR+17], notes 
Friday 
Dec 8 
1012 
1537 
23. 
Clique lower bound for regular resolution (cont.); course wrapup 
[ABdR+17], notes 
We will mostly be following the book
at least for the first half of the course.
While AroraBarak 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 outofdate 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.
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 paywall, 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.

[ABdR+17]
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende,
Massimo Lauria, Jakob Nordström, and Alexander Razborov:
Clique Is Hard on Average for Regular Resolution.
To appear in
Proceedings of the 50th Annual ACM Symposium on Theory of Computing
(STOC '18),
June 2018.

[CKLM17]
Arkadev Chattopadhyay, Michal Koucký,
Bruno Loff, and Sagnik Mukhopadhyay:
Simulation Theorems via
Pseudorandom Properties.
arXiv,
technical report
1704.06807,
2017.

[GPW15]
Mika Göös, Toniann Pitassi, and Thomas Watson:
Deterministic
Communication vs. Partition Number.
In Proceedings of the 56th Annual IEEE Symposium on
Foundations of Computer Science (FOCS '15),
pages 1077–1088,
2015.

[Pud97]
Pavel Pudlák:
Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations.
Journal of Symbolic Logic,
volume 62, issue 3, pages 981–998, 1997.
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.
