Complexity Theory
WiSe2024/25 Course codes: BGeA12→KTH12 ·MKLOG12K→KTH12
 External links:
Overview
Description
Complexity Theory is a beautiful field that studies different models of computation as well as their relationships to each other. The most famous open problem in this field is the P vs. NP problem. In this course, you will discover elegant proof techniques, fascinating ideas, and exciting open questions. The highlights of this course include:
 Complexity classes: Logspace, NP, BPP, polynomialtime hierarchy, ACC0, EXP, NEXP, NP/poly, #P, etc.
 KarpLipton’s Theorem, Hardness vs. Randomness, NEXP ⊈ ACC0, PCP theorem, etc.
This course is taught in English, and it is available for Bachelor and Master students!
Staff
 Holger Dell (professor); Office hours: most Mondays at 1415 in Room 302, RobertMayerStr. 1115.
 Julian Brinkmann (teaching assistant)
 Claudia Gressler (secretary)
Time and Place
 Moodle: Please register at the MoodlePage.
 First Session: Monday, October 14th, 2024 at 10:15.
 Lectures: Monday 1214, Wednesday 1416.
 Tutorials: Monday 1012.
 Location: Hörsaal H1, Hörsaalzentrum Bockenheim, 60325 Frankfurt am Main.
 Format: Inperson lectures and tutorials.
 Time commitment: 10 ECTS with 25h each = 250h. Subtracting 50 hours of exam preparation, we arrive at 14h per week. Of these, 4h are lectures, 2h are exercise groups, and 8h are selfstudy.
Learning activities
Your grade in this course will be based on your performance on learning activities throughout this course and the final exam. For each activity, you will receive constructive feedback. After receiving feedback, you get the chance to revise your work and improve your performance.
 Exercises. We provide many exercises that you are encouraged to solve in groups or alone. Unless the exercise is used for an assignment, you cannot hand in written solutions to these exercises. However, you can ask questions about them in class or in the tutorial sessions.
 Assignments. Assignments are specially marked exercises for which you are expected to hand in written solutions. You can discuss the solutions in groups beforehand. Your submission must be written in LaTeX using this LaTeXtemplate and handed in on the MoodlePage by Monday at 10:00. You will receive feedback on your submission and have the chance to revise it based on this feedback.
 Oral miniexam. On a regular basis, you will be evaluated in an oral miniexam of at most 15 minutes each on the contents from the previous three weeks. We will talk about the results and proofs from the book, as well as possibly the assignments you submitted.
 Presentations. Depending on what grade you want to earn, you are expected to give one or multiple oral presentations of at most 15 minutes during the lecture and during the tutorial session.
Evaluation rubrics
The assignments you submit will be evaluated using the following rubric:
 E: Exemplary. The solution consists of a clear, correct, and complete proof that not only contains no major errors (computation, logic, syntax, or semantic), it is also exceptionally clear, and the writeup is professional in its look and style. The solution would be at home in a professional lecture or publication.
 M: Meets Expectations. The solution consists of a clear, correct, and complete proof that contains no major errors (computation, logic, syntax, or semantic) and which is neatly and professionally written.
 R: Revision Needed. The solution contains at least one significant logical error or gap and requires revision. An R may also be given for writeups that do not expend sufficient effort to produce a goodlooking writeup.
All other activities, such as miniexams and presentations, are evaluated as follows:
 S: Satisfactory. The student has demonstrated a satisfactory understanding of the material.
 U: Unsatisfactory. The student has not demonstrated a satisfactory understanding of the material.
Collaboration and AI rules
You are encouraged to
 discuss the course material and the exercises with your fellow students, including the assignment problems, and
 use AI tools to help you understand the course contents. For example, if there’s a concept or a proof in the book that you did not fully understand, you can explain your issue to the AI tool and ask it to help you with any misunderstandings. AI tools are often wrong, so be skeptical.
The assignments you submit must be your own work, otherwise you will not learn much. Therefore, you are not allowed to
 share your written solutions for the assignments with others,
 read any parts of written solutions that are provided by other students or by AI tools, or
 use AI tools to outright solve the assignments; describing the assignment problem to the AI tool is considered a violation of this rule.
Grading
Satisfactory performance during the oral exam is required to pass the course. To pass the oral exam, you need to prove that you can explain your own submissions and reproduce the basic course contents from the entire syllabus. Your grade is mostly based on the demonstration of your learning during the semester. In total, this course will have 12 assignments and 4 oral miniexams. Each week, you can submit solutions to at most two assignments: for example, one new solution and one revision on an old solution. After February 10, no further submissions or revisions are possible! Here is how your grade will be determined:
grade  minimum required performance 

sehr gut 

gut 

befriedigend 

ausreichend 

 Important Remark: This table is subject to change!
 Your final grade may contain further gradations (1,7 vs 2,3, etc.), which are determined by the oral exam (if you pass), your engagement with the course (attendance, interaction), and if you are close to the thresholds according to the above scheme.
Week plan
The winter term has 15 weeks, the following is a preliminary plan copied from an old iteration of this course. Please expect changes! Note: This will not be updated, see Moodle for the most recent information.
 14. October – 18. October1 Introduction: Course structure, grading scheme, and the first assignment.
 21. October
–
25. October2
Efficient universal Turing machineAB 1.21.4, 1.61.7 · Inclass exercises: Example 1.1, Claims 1.5 and 1.6. · Exercises: 1.5, 1.6*, 1.9, 1.10, 1.15 (* = hard, but well worth the effort)
 28. October
–
1. November3
NP and NP completenessAB 2.12.3, 2.52.7 · Exercises: 2.10, 2.8, 2.25, 2.29, 2.6b*, 2.30*
 4. November
–
8. November4
DiagonalizationAB 3 · Exercises: 3.5, 3.6, 3.7*, 3.8*
 11. November
–
15. November5
Space complexityAB 4 · Exercises: 4.1, 4.2, 4.3, 4.7
 18. November
–
22. November6
The polynomial hierarchy and alternationsAB 5 · Exercises: 5.3, 5.7, 5.10, 5.13
 25. November
–
29. November7
Boolean circuitsAB 6 · Exercises: 6.3, 6.8, 6.9*, 6.12
 2. December
–
6. December8
Randomized computationAB 7 · Exercises: 7.4, 7.7, 7.9
 9. December
–
13. December9
Interactive proofsAB 8.18.3 · Exercises: 8.1, 8.2, 8.6*
 16. December – 20. December10 Recap: Review and Assessment
 13. January
–
17. January11
PCP TheoremAB 11 · Exercises: Read!, 11.2, 11.3, 11.6, 11.9*, 11.15
 20. January
–
24. January12
Decision TreesAB 12 · Exercises: 12.1, 12.2, 12.3, 12.6
 27. January
–
31. January13
Complexity of CountingAB 17 · Exercises: 17.2, 17.4, 17.6*
 3. February
–
7. February14
⊕ ∉ AC0AB 14.1
 10. February – 14. February15 Final week: Review and Assessment
Literature
AB: Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak.
[full text as EBook].
There is also a pdf on the book website, but be aware that it is not a final draft and has different chapter numbers.
Further resources
 Similar Courses:
 Dieter van Melkebeek’s Complexity Theory at UW Madison.
 Ryan Williams’ Automata, Computability, and Complexity Theory and Advanced Complexity Theory at MIT.
 For background reading on Turing machines, see:
 video lecture on chapter 6 in Jeff Erickson’s Models of Computation course.
 video lectures in Michael Sipser’s course at MIT.
 Also see TCS @ Princeton.