Curriculum M1 MPRI at ENS Paris-Saclay

ADCO: Advanced Complexity

Description: Complexity theory extends well beyond the concept of NP-completeness. The aim of this course is to examine a number of other fundamental constructs in complexity theory, such as space complexity and the concepts of alternating or randomized machines. We will explore some fascinating theorems, for instance, the equivalence between alternating time and deterministic space, or Shamir's IP=PSPACE theorem.

See real-time course progression for up-to-date information, including examination modalities.

Outline:

  1. Deterministic and non-deterministic machines. Compression theorems.
  2. Non-deterministic space, NL, PSPACE, Savitch's theorem.
  3. Log-space reductions, NL-complete problems, NP-complete problems.
  4. Alternating machines, Kozen-Meyer-Stockmeyer theorems. Circuits, Horn clauses, and P-complete problems.
  5. Oracles. The polynomial hierarchy, the Boolean hierarchy.
  6. Counting problems, #P-completeness.
  7. Randomized Turing machines. The classes RP, coRP, ZPP.
  8. The class BPP. The class P/poly. Karp-Lipton and Adleman theorems.
  9. Jeux d'Arthur contre Merlin. Le théorème de Babai.
  10. Preuves interactives. Le théorème de Golwasser-Sipser. Le théorème de Boppana--Håstad-Zachos.
  11. Les classes ABPP et IP. Le théorème de Shamir.
  12. Une introduction aux problèmes d'approximation et à la classe PCP.


References:

  • Sylvain Perifel. Complexité algorithmique. Ellipses, 2014, 432 pages. ISBN:978-2-729-88692-9.
  • Sanjeev Arora et Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. ISBN: 978-0-521-42426-4