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. The highlights of this course include:

• 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.

This course is taught in English, and it is available for Bachelor and Master students!

Staff

• Holger Dell (professor); Office hours: most Mondays at 14-15 in Room 302, Robert-Mayer-Str. 11-15.
• 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 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 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.
• Oral mini-exam. On a regular basis, you will be evaluated in an oral mini-exam 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 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 mini-exams 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 mini-exams. 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:

• If you only want to pass half of the course (KTH1), you need to fulfil at least half of the requirements (rounded up to the next integer).
• 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:

• 14. October – 18. October1 Introduction, Turing machines, time complexity: Course structure, grading scheme, and the first assignment.
  AB 1.2-1.4, 1.2, 1.3, 1.6 · Assignment: Ex. 1.5 or 1.6 · Exercises: Ex. 1.9, 1.10, 1.11 · Presentations: Claim 1.5, 1.6, 1.8
• 21. October – 25. October2 Efficient universal Turing machine
  AB 1.4, 1.7 · Assignment: Ex. 2.6(b)
• 28. October – 1. November3 NP and NP completeness
  AB 2.1-2.3, 2.5-2.7 · Assignment: Ex. 2.30 · Exercises: 2.10, 2.25, 2.29 · Presentations: Theorem 2.6, Lemma 2.11
• 4. November – 8. November4 Diagonalization
  AB 3 · Assignment: Ex. 3.7 · Exercises: 3.5, 3.6, 3.8 · Presentations: Theorems 3.2, 3.3, 3.7
• 11. November – 15. November5 Space complexity
  AB 4 · Assignment: Ex. 4.11 · Exercises: 4.2, 4.3, 4.7, 4.8 · Presentations: Theorem 4.13
• 18. November – 22. November6 The polynomial hierarchy and alternations
  AB 5.1-5.3 · Assignment: Ex. 5.7 · Exercises: 5.3, 5.10, 5.11
• 25. November – 29. November7 Boolean circuits
  AB 6 · Assignment: Ex. 6.5 · Exercises: 6.3, 6.8, 6.12
• 2. December – 6. December8 Randomized computation
  AB 7 · Assignment: Ex. 7.6 · Exercises: 7.4, 7.7, 7.9 · Presentations: Theorem 7.15
• 9. December – 13. December9 Interactive proofs
  AB 8.1-8.3 · Assignment: Ex. 8.6 · Exercises: 8.1, 8.2, 8.4
• 16. December – 20. December10 Recap and assessment
• 13. January – 17. January11 Complexity of counting
  AB 17 · Assignment: 17.2 · Exercises: 17.1, 17.4
• 20. January – 24. January12 Decision trees
  AB 12 · Assignment: Ex. 12.2 · Exercises: 12.1, 12.3, 12.6
• 27. January – 31. January13 ⊕ ∉ AC0
  AB 14.1 · Assignment: Ex. 14.2 · Exercises: 14.1, 14.3, 14.7
• 3. February – 7. February14 PCP theorem
  AB 11 · Exercises: 11.1, 11.2, 11.3, 11.6
• 10. February – 14. February15 Final week: Recap and Assessment

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.