Complexity Theory
WiSe2024/25 Course codes: BGeA12→KTH12 ·MKLOG12K→KTH12
 External links: qis
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.
Time and Place
 Moodle: Please register at the MoodlePage (link to be announced).
 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, but you are not allowed to share or read any parts of the writing of other students. 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 1520 minutes during the lecture and during the tutorial session.
Evaluation rubrics
The assignments you submit will be evaluated using the EMRN rubric. The following criteria help to assign the grade:
 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.
 N: Not assessable. It is not possible to assess this submission. For example, large portions of the solution are missing; or the solution is for a significantly altered version of the problem; or the student has submitted solutions to more than one problem; or the submission is excessively cluttered, messy, or difficult to read.
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.
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 10 assignments and 20 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.
 Introduction.
Course structure, grading scheme, and the first assignment.  Efficient universal Turing machine. [AB 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)  NP and NP completeness [AB ch. 2.12.3, 2.52.7]
Exercises: 2.10, 2.8, 2.25, 2.29, 2.6b*, 2.30*  Diagonalization [AB, ch. 3]
Exercises: 3.5, 3.6, 3.7*, 3.8*  Space complexity [AB, ch. 4]
Exercises: 4.1, 4.2, 4.3, 4.7
Assignment: pdf  The polynomial hierarchy and alternations [AB, ch.5]
Exercises: 5.3, 5.7, 5.10, 5.13  Boolean circuits [AB, ch. 6]
Exercises: 6.3, 6.8, 6.9*, 6.12  Randomized computation [AB, ch.7]
Exercises: 7.4, 7.7, 7.9
Assignment: pdf.  Interactive proofs [AB, ch. 8.18.3]
Exercises: 8.1, 8.2, 8.6*  PCP Theorem [AB, ch. 11]
Exercises: Read!, 11.2, 11.3, 11.6, 11.9*, 11.15  Decision Trees [AB, ch. 12]
Exercises: 12.1, 12.2, 12.3, 12.6  Complexity of Counting [AB, ch. 17]
Exercises: 17.2, 17.4, 17.6*
Assignment: pdf.  ⊕ ∉ AC0 [AB, ch. 14.1]
 NEXP ⊈ ACC0 [AB, addendum · paper]
 To be announced.
 Final Assessment Week
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.
[Volltext als 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.