Lecture 1: Overview
- Formal definition of a proof system
- Examples of proof systems
- Tree-like resolution lower bound
- Prover-Delayer game [PI99]
- Ordering principle
Lecture 2: Resolution
- Length vs width
- Small width -> small length
- Small length -> small width [BW01]
- Trade-offs
- Width lower bound
- Tseitin formula
- Spoiler-Duplicator game [AD08]
Lecture 3: Polynomial Calculus
- Definition of PCR
- Size vs degree
- Small degree -> small size [CEI96]
- Small size -> small degree [IPS99]
Lecture 4: Polynomial Calculus
- Degree lower bound [BI10]
- Tseitin formula
- Gaussian width
Lecture 5: Sums of Squares
- Definition of Nss, SA, SoS, Pss
- Degree lower bound
- Tseitin formula
- Pseudoexpectation
Lecture 6: Interpolation