Séminaires : Séminaire des Thésards

Equipe(s) : doctorants,
Responsables :Andrei Bengus-Lasnier, Eleonora Di Nezza, Ilias Ftouhi, Mario Gonçalves, Mahya Mehrabdollahi, Romain Petrides, Arnaud Vanhaecke
Email des responsables :
Salle :
Adresse :
Description

Le séminaire des thésards est l'occasion pour les doctorants de présenter des résultats et des problématiques dignes d'intérêt devant un public de non-spécialistes. L'ambiance y est informelle ; poser des questions naïves est encouragé, et les questions moins naïves sont bienvenues dans la mesure où elles n'entravent pas le bon déroulement de l'exposé.

Un mercredi sur deux à 17 h, en alternance entre Jussieu et Sophie Germain.


Orateur(s) Maud SZUSTERMAN - IMJ-PRG,
Titre Complexités des fonctions booléennes sur l'hypercube
Date06/11/2019
Horaire17:00 à 18:00
Résume

Imaginons un vote de N participants, qui prend la valeur 1 si la majorité a répondu oui, et la valeur -1 sinon. Le résultat du vote va-t-il etre modifié si une erreur de transmission est commise sur une fraction epsilon des N participants ? La plupart du temps, non. On dira que la fonction "Majorité" est stable, ou insensible "au bruit". (A l'inverse, en physique statistique, certaines configurations géométriques, définies en se plaçant au paramètre critique, sont hautement sensibles à de petites modifications locales. ) Une des premières "mesures" proposées pour quantifier "la complexité" d'une fonction booléenne, est la sensibilité dite locale, notée s(f), introduite par Cook et Dwork lors de leur étude de certains processeurs appelés CREW PRAM. Peu de temps après, Noam Nisan propose une autre mesure, la sensibilité par blocs, qui caractérise la difficulté de calcul qui intéressait Cook et Dwork. Depuis, cette dernière a été montrée polynomialement équivalente à d'autres mesures de complexité, telles que la complexité par certificat, celle par arbre de décision, ... Pendant des dizaines d'années, personne ne parvenait à montrer que la sensibilité locale s(f) était elle aussi dans cette classe d'équivalence (cette appartenance conjecturée s'appelle conjecture de Nisan et Szegedy). Par un argument simple et joli de théorie des graphes, et en utilisant une reformulation combinatoire de la conjecture (due à Gotsman et Linial), H. Huang a finalement prouvé la conjecture de Nisan et Szegedy : nous discuterons sa preuve après avoir introduit les différentes notions.

Salle15-16-413
AdresseJussieu
© IMJ-PRG