Lecture 1 : Speedup theorem
Outline
Advanced Complexity (M1 ENS Paris-Saclay / ENS Ulm)
- Teachers:
- Teaching assistants:
- Course pages:
Exercises 1 : SPACE and NL
EX 1: Graph representation and why it doesn’t matter
Lecture 2: Logspace
Webpage of the course
Exercises 2 : SPACE and NL (2)
EX 1 : Warm up
Lecture 3:
Immermann-Szelepcsenyi (1987)
Exercises 3: Space hierarchy theorem
EX 1: Space hierarchy theorem
Exercises 4: PSPACE-complete problems, Padding
EX 1: Language theory
Lecture 5: P=AL
Last week:
Exercises 5: Prime Numbers, P-complete problems
EX 1: Unary languages
DM: Advanced Complexity
Homework Assignment : Advanced complexity.
Lecture 6: Polynomial-time hierarchy
A visit to the polynomial-time hierarchy
Lecture 7: RP, coRP, ZPP, BPP
RP, coRP, ZPP, BPP
Exercises 10: BPP, AM protocols, AM hierarchy
EX0: BPP-completeness
Lecture 8: BPP, P/Poly
Karp-Lipton
Exercises 11: BPP, ABPP, PP
Proofs to bear in mind
Lecture 9: The PCP theorem
cf. CSE 533: The PCP Theorem and Hardness of approximation (autumn 2005)
Exercises 12: Review
NP, coNP