Lecture notes:

• Lecture 1: Introduction.
• Lecture 2: Faster-than-2ⁿ algorithms (Part I). (Updated 29.01.)
• Lecture 3: Faster-than-2ⁿ algorithms (Part II). (Updated 29.01.)
• Lecture 4: The Exponential Time Hypothesis. (Updated 29.01.)
• Lecture 5: The Resolution proof system.
• Lecture 6: Conflict-driven clause learning.
• Lecture 7: Exponential size lower bounds for Resolution.
• Lecture 8: Cutting Planes and other proof systems.
• Lecture 9: Frege and Extended Frege systems.
• Lecture 10: Exponential-size lower bounds for Cutting Planes. Short proofs of PHP in Frege systems.

Other courses: Archive.