Cours de L3 "Complexité avancée", 2ème partie

The course is based on the following lecture notes: polycopié (1st part) and polycopié (2nd part).

The first part is taught by Philippe Schnoebelen, and the exercice sessions are given by Guillaume Scerri.

The slides of the second part of the course:

• Randomized Turing machines, RP, coRP, ZPP: covers Sections 1.1 and 1.2 of the polycopié (2nd part); the shorter version, and the video (November 4th, 2020);
• BPP (part 1): covers Section 1.3 and the Sipser-Gács-Lautemann theorem (Proposition 1.24) of the polycopié (2nd part); the shorter version, and the video;
• BPP (part 2): covers Section 1.4 (except for the Sipser-Gács-Lautemann theorem) of the polycopié (2nd part); the shorter version, and the video;
• Arthur vs. Merlin games (part 1): covers Section 3 up to and including Section 3.1 of the polycopié (2nd part); the shorter version, and the video;
• Arthur vs. Merlin games (part 2): covers Section 3.2 of the polycopié (2nd part); the shorter version, and the video;
• Sipser's coding lemmas, and consequences: covers Section 3.3 and Section 3.4 of the polycopié (2nd part); the shorter version; the video, covering this, plus the beginning of the next series (including ABPP⊆IP⊆PSPACE);
• Shamir's theorem: covers Section 3.5 of the polycopié (2nd part); the shorter version; and the video, covering the hard direction PSPACE⊆ABPP.
• NP=PCP and hardness of approximation: covers a good deal of Section 2 of the polycopié (2nd part); the shorter version.