# Course: Complexity Theory

## Winter 2017/18

### Course Outline

This is an introductory course in computational complexity theory. It is introductory in the sense that no prior knowledge in complexity theory is assumed. However, I do assume a basic understanding of algorithms and familiarity with the basics of theory of computation. For example, I assume you know the Big-O notation, algorithms on graphs (breadth first search, depth first search), regular languages and finite automata, and that you have seen Turing machines and know what is P and NP. The latter concepts will also be introduced and reviewed in the course.

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.

**Text book** Arora and Barak, Computational Complexity: A Modern Approach. 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.

### General Information

**Professor:**Rupak Majumdar (rupak@mpi-sws.org) Office: Room 414, MPI Building (26 Paul-Ehrlich-Str). Office hours: by appointment.**Teaching Assistant:**Kaushik Mallik (kmallik@mpi-sws.org).**Mailing list:**ct-ws17@lists.mpi-klsb.mpg.de**Lectures:**Monday 15:30 - 17:00 in 46-280 and Wednesday 13:45 - 15:15 in 46-268.**Tutorial:**Tuesday 14:00-15:00, Room 113**Office hour:**Wednesday 08:30-09:30, Room 310**Final Exam:**14.03.2018, 08:30-11:00, Room 46-110**Evaluation:**based on final written exam.**Homework Requirement:**In order to attend the final exam, you have to turn in regular homework assignments. 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.

### Announcements

- There is going to be a written exam at the end of the ongoing semester (SS 2018). Following are the logistics:
- Date: August 27, 2018
- Time: 09:30-12:00
- Venue: MPI-SWS (Paul-Ehrlich-Str. 26), Room 207

### Homework assignments

### Additional problems from last year's course

Last year's final exam paper final.pdf

Few more problems problems.pdf and answers (incomplete) answer.pdf

### Syllabus (tentative)

Readings refer to Arora-Barak. In addition, we will post notes on individual lectures throughout the course of the semester. Feedback and corrections on the lecture notes are always appreciated!

**[Date: 30.10.2017 and 06.11.2017]**- 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.

- Introduction; review of Turing machines; P and NP; NP-completeness
**[Date: 08.11.2017 and 13.11.2017]**- Cook-Levin theorem (proof). NP-completeness continued. NP and coNP. Structure of NP. Diagonalization.
**Reading:**Chapter 2.

- Cook-Levin theorem (proof). NP-completeness continued. NP and coNP. Structure of NP. Diagonalization.
**[Date: 15.11.2017 and 20.11.2017]**- Diagonalization. Hierarchy theorems. Ladner's theorem. Oracles and relativization.
**Reading:**Chapter 3. We followed the first proof here of Ladner's theorem.

- Diagonalization. Hierarchy theorems. Ladner's theorem. Oracles and relativization.
**[Date: 22.11.2017 and 27.11.2017]**- Space Complexity: PSPACE, L, NL. QBF is PSPACE-complete. Logspace reductions. PATH is NL-complete. Savitch's theorem.

**[Date: 29.11.2017 and 04.12.2017]**- NL = coNL. NFA-universality. P-completeness. Alternation. Polynomial hierarchy.

**[Date: 06.12.2017 and 11.12.2017]**PH using oracles. Circuits. P/poly. Karp-Lipton theorem. Non-uniform complexity. Kannan's theorem. Link to the original paper.

**[Date: 13.12.2017 and 18.12.2017]**- Parity is not in AC0. (Theorem 14.4 in Arora-Barak.)

**[Date: 20.12.2017 and 08.01.2018]**- Randomized computation. RP, BPP. Probabilistic inequalities. Schwarz-Zippel lemma and polynomial identity testing.

**[Date: 10.01.2018 and 15.01.2018]**- Interactive proofs. MA and AM. Interactive proof for coNP.

**[Date: 17.01.2018 and 22.01.2018]**- IP = PSPACE.

**[Date: 24.01.2018 and 29.01.2018]**- Cryptography. One-way functions. Encryption from one-way functions. Pseudo-randomness.
Lecture notes by Dr. Marko Horvat: CryptographyLectureNote.pdf

- Cryptography. One-way functions. Encryption from one-way functions. Pseudo-randomness.
**[Date: 31.01.2018 and 05.02.2018]**- Counting complexity. #P. Toda's theorem.

**[Date: 07.02.2018]**- PCP theorem. Wrap-up.