Computational complexity
CS-524
Media
This file is part of the content downloaded from Computational complexity.
- Announcements (Forum)
- Textbook: Computational Complexity: A Modern Approach (URL)
- Office hours (on demand) (Page)
- Ed Discussion - Forum for all Q&A (External tool)
- Video archive link (old videos - some broken!) (URL)
- Final exam - Model solutions (File)
- Exam grade review (Page)
11 September
Part 1: Structural Complexity
Lecture 1: Introduction to P vs NP
Chapter 1 and 2.1 in Arora-Barak
- Intro (Course organisation) (File)
- Lecture 1 - Slides (File)
- Exercise set 1 (File)
- Exercise set 1 - Solutions (File)
18 September
Lecture 2: NP-completeness
Chapter 2 (excluding proof of Cook-Levin) in Arora-Barak
- Lecture 2 - Slides (File)
- Exercise set 2 (File)
- Exercise set 2 - Solutions (File)
- Video of the week: Hackerdashery on P vs NP (URL)
Bonus
Bonus material: More NP-completeness
This video establishes the NP-completeness of 3-Matching and Subset Sum problems. The material is considered supplementary: details of the reductions will not be asked in the Final Exam, but they do give you more experience with NP-completeness proofs.
- 30-min video on 3-Matching and Subset Sum (URL)
- NP-hardness of 3-Matching (source: Nature of Computation, p.155) (File)
25 September
Lecture 3: Circuit Complexity and Cook–Levin
Chapters 6.1 and 6.2 for circuits.
First homework will be released Monday 29 September with deadline Wednesday 8 October.
- Lecture 3 - Notes (File)
- Exercise set 3 (File)
- Exercise set 3 - Solutions (File)
- Video of the week: Stephen Cook talks about his famous result! (URL)
- Homework 1 (Assignment)
- Solutions for Homework 1 (File)
2 October
Lecture 4: Diagonalisation and Oracles
Chapter 3.
9 October
Lecture 5: Space Complexity
Chapter 4.
- Lecture 5 - Notes (File)
- Exercise set 5 (File)
- Exercise set 5 - Solutions (File)
- Link of the week: Time vs. Space Breakthrough 🤯 (URL)
16 October
Lecture 6: Polynomial Hierarchy
Chapter 5.
- Lecture cancelled (teacher sick 🤧)
- ...but link to a video recording from 2022
October 23 - Reading week
No lecture on reading week.
30 October
Lecture 7: Randomised Complexity
Chapter 7.
- Lecture 7 - Notes (File)
- Exercise set 7 (File)
- Exercise set 7 - Solutions (File)
- Homework 2 (Assignment)
- Homework 2 with solutions (File)
6 November
Part 2: Concrete Complexity
Lecture 8: Decision trees
Chapter 12.
13 November
Lecture 9: Proof complexity
Jukna, Chapter 18 (link below)
- Lecture 9 - Notes (File)
- Exercise set 9 (File)
- Exercise set 9 - Solutions (File)
- Book chapter from "Boolean Function Complexity" by Stasys Jukna (File)
- Super-bonus video: Lecture 1 from a currently-ongoing proof complexity course by Jakob Nordström (URL)
20 November
Lecture 10: Communication Complexity
Chapter 13.
Third homework released around 26 November
27 November
Lecture 11: Set-Intersection, Applications
Rao-Yehudayoff, beginning of Chapter 9 (see link below)
- Excerpt from Rao-Yehudayoff (File)
- Lecture 11 - Notes (File)
- Exercise set 11 (File)
- Exercise set 11 - Solutions (File)
- Homework 3 (Assignment)
- Homework 3 - Solutions (File)
4 December
Recap Lecture
We'll go over the Final Exam from last year. (No exercise session.)
Below you'll also find some random past exams (mostly found online) that you can use to train your inner complexity theorist.
Note that the following may contain material that we have not covered in our course this year.
- Final exam 2024 (File)
- Final exam 2024 - Solutions (File)
- Final exam 2023 (File)
- Final exam 2023 - Solutions (File)
- Final exam 2022 (File)
- Final exam 2022 - Solutions (File)
- Final exam 2021 (File)
- Final exam 2021 - Solutions (File)
- Petting Zoo 🐇: Review of the most important complexity classes (we didn't cover all of these) (URL)
- Anup Rao (University of Washington) exam from 2020 (URL)
- Anup Rao (University of Washington) exam from 2020 - Solutions (File)
- Paweł Parys (University of Warsaw) exam from 2018 (URL)
- Paweł Parys (University of Warsaw) exam from 2020 (URL)
- Ola Svensson (EPFL) exam from 2018 (many topics we didn't cover) (File)
- Ola Svensson (EPFL) exam from 2016 (we didn't cover PCPs) (File)
11 December
Final Exam
- Location: CE 1 106
- Time: 3:15pm-6:15pm
- Closed book: No cheat sheets allowed!