Cours de complexité II, ENS Cachan 1ère année

Jean Goubault-Larrecq
LSV/UMR 8643, CNRS, ENS Cachan & INRIA Futurs projet SECSI
61 avenue du président-Wilson, F-94235 Cachan Cedex
goubault@lsv.ens-cachan.fr
Phone: +33-1 47 40 75 68   Fax: +33-1 47 40 75 21


    Cours
Où? Where? Bât. Cournot, C205
Quand? When? Le vendredi de 14h00 à 16h30
Par qui? Who? Jean Goubault-Larrecq (cours)
    Fabrice Chevalier (TD)

Ce cours est la suite du cours de calculabilité et complexité du premier trimestre, par Hubert Comon-Lundh et Jean Goubault-Larrecq.

Il a lieu en alternance avec les TD, un vendredi sur deux. Programme: Attention, il risque d'y avoir une réorganisation des dates des TD 6-7 et du cours 7.

Il y a un poly pour tout ce qui est classes randomisées (cours 4-7). La démonstration du théorème d'Arora-Safra y est juste esquissée, et j'ai des doutes quant à sa correction. (Je n'ai plus besoin de l'ingrédient pourtant censément essentiel, de composition des prouveurs.) Je ne fais pas la démonstration du théorème de Goldwasser-Sipser en cours... trop compliqué, je trouve.

Pour les cours précédents, voir le poly de Ralf, accessible depuis la page de son cours de complexité. En particulier, la section 5.2 pour le cours 3, et le chapitre 9 pour les cours 1 et 2.

Examen le vendredi 02 juin, même endroit, mêmes heures. Jusque là, le devoir! A rendre le vendredi 02 juin. Inutile de chercher à le finir lors de l'examen, vous n'aurez pas le temps. C'est l'examen qui comptera pour la note, le devoir comptera essentiellement comme rattrapage... et comme entraînement à l'examen bien sûr.

Quelques sujets d'examens sur des sujets connexes que j'ai posés dans le temps:
This document was translated from LATEX by HEVEA.