- Lectures
- Omar Fawzi
- Wednesday 13:30
- changes every week

- Tutorials
- Fabrice Mouhartem
- Tuesdays 15:45
- changes every week

- Models of computation. Time and space classes.
- Randomized complexity classes
- Boolean circuits
- Interactive proofs
- One of the following topics: communication complexity, quantum complexity theory, Hardness of approximation and PCPs

- [AB] Computational complexity: A modern approach
- [Per] Complexite algorithmique (in French)

- A final exam
- Several homeworks
- One midterm exam
- Writing a wikipedia article (bonus)

Date | Topic | References |

Feb 15th | The class P and the class NP. Nondeterministic Turing machines, equivalent definition of NP. NP-hardness. Example NP-complete problem. Statement of NP-completeness of SAT |
Lecture notes (from 2014 offering) Chap 1 of [AB], Sec 2.1, 2.2 and beginning of 2.3 of [AB] |

Mar 1st |
Proof that SAT is NP-hard. (Check these notes for a proof of NP-completeness of SAT for a RAM model.) Class coNP. NP and coNP are in EXP. Deterministic time hierarchy theorem. |
Chap 2 et 3.1 of [AB] |

Mar 8th | Space complexity. L, NL, PSPACE. Relation to time classes. TQBF is PSPACE complete. | Chap 4.1 and 4.2 of [AB] |

Mar 15th | Proof of PSPACE-completeness of TQBF. PSPACE = NPSPACE. NSPACE(S) in SPACE(S^2) (Savitch theorem). Class NL, NL-hardness PATH is NL-complete. Stated NL = coNL. |
Sec 4.2 and 4.3 (space complexity) of [AB] |

Mar 22th | Proof NL = coNL. Oracle Turing machines. Statement of existence of oracles A,B with P^A=NP^A and P^B \neq NP^B | Chap 4 and Sec 3.4 of [AB] |

Mar 29th |
Proof of existence of oracles A,B with P^A=NP^A and P^B \neq NP^B. Polynomial hierarchy with alternating quantifiers and with oracle machines. If \Sigma_i = \Pi_i then the hierarchy collapses. Definition of polynomial hierarchy with oracles. |
Sec 3.4, 5.1, 5.2, 5.5 of [AB] |

Apr 5th | Boolean circuits, P included in P/poly, uniformity condition for circuit family TMs with advice, Karp-Lipton theorem: If NP included in P/poly, then the polynomial hierarchy collapses. |
Sec 6.1, 6.2, 6.3, 6.4 of [AB] |

Apr 12th | Finish Karp-Lipton Randomized computation: BPP, RP, error reduction, BPP \in P/poly, BPP in poly hierarchy. |
Sec 7.1, 7.3, 7.4, 7.5 of [AB] |

Apr 26th | Quantum states. Quantum circuits. Definition of the class BQP. P included in BQP. | Chap 20 of [AB]. See also Watrous' lecture notes on introduction to quantum computing. |

May 3rd |
BPP included in BQP.
BQP included in PSPACE. Evidence for quantum speedup: query complexity model. Simons problem. |
Chap 20 of [AB]. See also Watrous' lecture notes on introduction to quantum computing. |