Further, I expect you (1) have "mathematical maturity" (e.g., are comfortable with proofs and abstract reasoning); (2) are interested in the material; and (3) are willing to spend time outside of class in order to better understand the material presented in lectures.

Complexity theory is one of the most elegant branches of computer science. The goal of the course is to become familiar with some of the most beautiful results in our field.

Copies of the textbook will be available in the library. I will also provide lecture notes giving further details or covering topics not in that text.

If you are unsure whether this class is appropriate for you, I recommend you look at the Arora-Barak textbook to see whether you (a) find the topics interesting, and (b) find the level of difficulty appropriate.

The text book

Michael Sipser, *Introduction to the theory of computation*,

contains the material we will cover in the first few weeks as well as the required
background for the class.

**Professor:**Rupak Majumdar (rupak@mpi-sws.org) Office: Room 414, MPI Building (26 Paul-Ehrlich-Str). Office hours: by appointment.**Logistics**: The class meets Mondays 1530 - 1700 in 46-280 and Wednesdays 1345 - 1515 in 46-268.**Teaching Assistant:**Ivan Gavran (`gavran@mpi-sws.org`).**Tutorial:**Tuesdays 1330-1430 in 111 MPI Building. Office hours: Thursdays 1300-1400. Also, by appointment.**Homework Requirement**: In order to attend the final exam, you have to turn in regular homework assignments (at least 6 out of 8) and transcribe one lecture into latex. Class participation and attendance will be taken into account for borderline cases.**Academic Integrity**The work you submit in this course must be the result of your individual effort. You may discuss homework problems and general proof strategies or algorithms with other students in the course, but you must not collaborate in the detailed development or actual writing of problem sets. This implies that one student should never have in his or her possession a copy of all or part of another student's homework. It is your responsibility to protect your work from unauthorized access. In writing up your homework you are allowed to use any book, paper, or published material as long as you clearly cite your sources. If you discuss problems with other students, please mention their names in your solutions. You are not allowed to ask others for writeups of specific solutions, either in person or by using electronic forums such as newsgroups. During the administration of exams any form of cooperation or help is forbidden.Academic dishonesty has no place in a university; it wastes our time and yours, and it is unfair to the majority of students. Any dishonest behavior will be severely penalized and may lead to failure in the course.

- 17.11.2016: Homework 2 is online.
- Tutorials will start from 08.11.2016. (01.11.2016 is a holiday!). Additionally, we will have a special tutorial on 03.11.2016 to help with the homework.

**[Week 1: 24.10.2016 26.10.2016]**

Introduction; review of Turing machines; P and NP; NP-completeness**Reading:**Chapter 0; Chapter 1: 1.1-1.6; Chapter 2: 2.1, 2.2, 2.4.

**[Week 2: 31.10.2016 and 02.11.2016]**

Cook-Levin theorem (proof). NP-completeness continued. NP and coNP. Structure of NP. Diagonalization.

**Reading:**Chapter 2.

**[Week 3: 07.11.2016 and 09.11.2016]**

Diagonalization. Hierarchy theorems. Ladner's theorem. Oracles and relativization.**Reading:**Chapter 3. We followed the first proof here of Ladner's theorem.

**[Week 4: 14.11.2016 and 16.11.2016]**

Space Complexity: PSPACE, L, NL. QBF is PSPACE-complete. Logspace reductions. PATH is NL-complete. Savitch's theorem.

**[Week 5: 21.11.2016 and 23.11.2016]**

NL = coNL. NFA-universality. P-completeness. Alternation. Polynomial hierarchy.

**[Week 6: 28.11.2016 and 30.11.2016]**

PH using oracles. Circuits. P/poly. Karp-Lipton theorem. Non-uniform complexity. Kannan's theorem. Link to the original paper.

**[Week 7: 05.12.2016 and 07.12.2016]**

Parity is not in AC0. (Theorem 14.4 in Arora-Barak.)

**[Week 8: 12.12.2016 and 14.12.2016]**

Randomized computation. RP, BPP. Probabilistic inequalities. Schwarz-Zippel lemma and polynomial identity testing.

**[Week 9: 19.12.2016 and 21.12.2016]**

Interactive proofs. MA and AM. Interactive proof for coNP.

**[Week 10: 09.01.2017 and 11.01.2017]**

IP = PSPACE.

**[Week 11: 16.01.2017 and 18.01.2017]**

Cryptography. One-way functions. Encryption from one-way functions. Pseudo-randomness.

**[Week 12: 23.01.2017 and 25.01.2017]**

Counting complexity. #P. Toda's theorem.

**[Week 13: 30.01.2017 and 01.02.2017]**

PCP theorem.

**[Week 14: 06.02.2017 and 08.02.2017]**

PCP theorem. Wrap-up.