Sylvain Perifel (IRIF, Paris)

Tous les problèmes connus ont été dérandomisés. Tous ? Non, car un irréductible problème résiste encore et toujours… Dans cet exposé sur la puissance de l’aléatoire dans les algorithmes, au prétexte d’assiéger ce fameux problème « irréductible » du test d’identité de polynômes nous explorerons les liens entre bornes inférieures non uniformes et dérandomisation : nous verrons que des bornes inférieures sur la taille des circuits booléens pour certains problèmes permettent d’éliminer l’usage de l’aléatoire dans les algorithmes (« dérandomisation ») d’une part, et d’autre part que la dérandomisation de certains problèmes nécessite de montrer des bornes inférieures non uniformes… Ce trait d’union profond entre algorithmes probabilistes et bornes inférieures sur les circuits relie deux notions fondamentales en complexité algorithmique et mérite au moins une bonne garnison de Romains.