Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 11 Juin 2019

Circuix le Gaulois

par 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr