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.
Course Staff
 Holger Dell (professor)
 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 alone or in groups. 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.
 Tests. On a regular basis, tests will be written in class. Each test consists of one or multiple questions that ask you to reproduce or apply some parts of the material of the preceding weeks. If you miss a test or produce unsatisfactory answers, you can retake the test at a later point during the semester to earn credit for the test.
 Presentations. Depending on what grade you want to earn, you are expected to give one or multiple oral presentations of at most 15–20 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 tests 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. However, you must not share your written solutions for the assignments, and you must not read any parts of written solutions that are provided by other students or by AI tools. You are encouraged to use AI tools to help you understand the course contents, but you must not use AI tools to outright solve the assignments. Providing the text of 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 24 minitest questions. 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.
 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 complexity
 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 computation
 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 Counting
 3. February
–
7. February14
⊕ ∉ AC0AB 14.1
 10. February – 14. February15 Final week: Review and Assessment
Prerequisites
This course is available for Bachelor and Master students! You must have mastered Algorithms and Data Structures 1 and 2 (or equivalent).
Contents
 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.
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.