Sidebar
Complexité des circuits
Cours de 24h - 3 ECTS en seconde période.
Enseignant : Sylvain Perifel.
10 cours de 2h30 le vendredi à 12h45 en salle 2036 (bâtiment Sophie Germain).
Premier cours le vendredi 8 décembre 2017.
Le cours sera donné en français, sauf si au moins un étudiant demande l'anglais et que personne ne s'y oppose.
Le but de ce cours est d'étudier la complexité de langages ou de polynômes en termes de circuits booléens ou arithmétiques. L'accent sera mis sur la preuve de bornes inférieures. Des notions de complexité booléenne et une certaine aisance en algèbre (polynômes) sont requises.
Le contenu indicatif du cours est le suivant :
- Bornes inférieures en n^k à k fixé (Kannan, Vinodchandran, Baur et Strassen, Lipton)
- Bornes inférieures superpolynomiales pour des circuits restreints (Razborov et Smolensky, circuits monotones, circuits multilinéaires, Williams si le temps le permet)
- Liens avec la dérandomisation (si le temps le permet)
Une partie du contenu est couvert dans le livre Complexité algorithmique disponible en ligne.