Complexity Theory

• Course codes: B-GeA-12→KTH12 ·M-KLOG-12-K→KTH12
• External links:
  MoodleQIS

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 Moodle-Page.
• First Session: Monday, October 14th, 2024 at 10:15.
• Lectures: Monday 12-14, Wednesday 14-16.
• Tutorials: Monday 10-12.
• Location: Hörsaal H1, Hörsaalzentrum Bockenheim, 60325 Frankfurt am Main.
• Format: In-person 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 self-study.

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 LaTeX-template and handed in on the Moodle-Page 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 write-up 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 write-ups that do not expend sufficient effort to produce a good-looking write-up.

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:

• 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 machine
  AB 1.2-1.4, 1.6-1.7 · In-class 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 completeness
  AB 2.1-2.3, 2.5-2.7 · Exercises: 2.10, 2.8, 2.25, 2.29, 2.6b*, 2.30*
• 4. November – 8. November4 Diagonalization
  AB 3 · Exercises: 3.5, 3.6, 3.7*, 3.8*
• 11. November – 15. November5 Space complexity
  AB 4 · Exercises: 4.1, 4.2, 4.3, 4.7 · Assignment
• 18. November – 22. November6 The polynomial hierarchy and alternations
  AB 5 · Exercises: 5.3, 5.7, 5.10, 5.13
• 25. November – 29. November7 Boolean circuits
  AB 6 · Exercises: 6.3, 6.8, 6.9*, 6.12
• 2. December – 6. December8 Randomized computation
  AB 7 · Exercises: 7.4, 7.7, 7.9 · Assignment
• 9. December – 13. December9 Interactive proofs
  AB 8.1-8.3 · Exercises: 8.1, 8.2, 8.6*
• 16. December – 20. December10 Recap: Review and Assessment
• 13. January – 17. January11 PCP Theorem
  AB 11 · Exercises: Read!, 11.2, 11.3, 11.6, 11.9*, 11.15
• 20. January – 24. January12 Decision Trees
  AB 12 · Exercises: 12.1, 12.2, 12.3, 12.6
• 27. January – 31. January13 Complexity of Counting
  AB 17 · Exercises: 17.2, 17.4, 17.6* · Assignment
• 3. February – 7. February14 ⊕ ∉ AC0
  AB 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: Log-space, NP, BPP, polynomial-time hierarchy, ACC0, EXP, NEXP, NP/poly, #P, etc.
• Karp-Lipton’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 E-Book].

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.