Computational complexity
CS-524
Media
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)
- Video archive link (URL)
12 September
Part 1: Structural Complexity
Lecture 1: Introduction to P vs NP
Chapter 1 and 2.1 in Arora-Barak
19 September
Lecture 2: NP-completeness
Chapter 2 (excluding proof of Cook-Levin) in Arora-Barak
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)
26 September
Lecture 3: Circuit Complexity and Cook–Levin
Chapters 6.1 and 6.2 for circuits.
First homework released at the end of the week!
- 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 - Solutions (File)
3 October
Lecture 4: Diagonalisation and Oracles
Chapter 3.
- Lecture 4 - Notes (File)
- Exercise set 4 (File)
- Exercise set 4 - Solutions (File)
- Video of the week: Hackerdashery on P vs NP (URL)
10 October
Lecture 5: Space Complexity
Chapter 4.
17 October
Lecture 6: Polynomial Hierarchy
Chapter 5.
Reading week
31 October
Lecture 7: Randomised Complexity
Chapter 7.
- Lecture 7 - Notes (File)
- Exercise set 7 (File)
- Exercise set 7 - Solutions (File)
- Homework 2 - Solutions (File)
7 November
Part 2: Concrete Complexity
Lecture 8: Decision trees
Chapter 12.
14 November
Lecture 9: Proof complexity
Jukna, Chapter 18 (link below)
- Book chapter from "Boolean Function Complexity" by Stasys Jukna (File)
- Lecture 9 - Notes (File)
- Exercise set 9 (File)
- Exercise set 9 - Solutions (File)
21 November
Lecture 10: Communication Complexity
Chapter 13.
Third homework released at the end of the week!
- Lecture 10 - Notes (File)
- Exercise set 10 (File)
- Exercise set 10 - Solutions (File)
- Homework 3 - Solutions (File)
28 November
Lecture 11: Set-Intersection, Applications
Rao-Yehudayoff, beginning of Chapter 9 (see link below)
- Guest lecturer: Dmitry Sokolov
- Video archive (from previous years): https://theory.epfl.ch/mika/cc-recordings/
- Excerpt from Rao-Yehudayoff (File)
- Lecture 11 - Notes (File)
- Exercise set 11 (File)
- Exercise set 11 - Solutions (File)
5 December
Recap Lecture
We'll go over the Final Exam from last year.
- Zoom link: https://epfl.zoom.us/j/62906174924
Below you'll 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 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)
12 December
Final Exam
- Location: CM 1 3
- Time: 3:15pm-6:15pm
- Closed book: No cheat sheets allowed!