fren

Irit Dinur

Au programme de la matinée du 21 août, c'est au tour de la jeune mathématicienne israélienne Irit Dinur d'entrer en scène.

Le titre de l'exposé est Probabilistically checkable proofs and codes mais avant d'entrer dans le vif du sujet, Irit Dinur nous invite à nous poser toutes sortes de questions préliminaires : qu'est-ce qu'une preuve ? quelle est la différence entre un problème et sa solution ? entre un théorème et sa démonstration ? ...

Pour la suite, l'idée est de pouvoir s'assurer de la validité d'une preuve sans la vérifier entièrement, en s'appuyant sur les probabilités.

Le coup de la confiture

Imaginez que vous êtes aveugle et que l'on vous présente une tartine de pain sur laquelle il y a peut-être un tout petit peu de confiture concentré sur une toute petite zone, presqu'un point. Vous pouvez goûter la tartine pour savoir s'il y a effectivement de la confiture dessus, mais le risque de vous tromper est grand : facile de mordre une zone non garnie et d'en déduire à tort qu'il n'y a rien sur la tartine. Vous pouvez aussi tartiner avec votre couteau. Si la tartine n'a pas de confiture vous tartinez de l'air (pas grave, le ridicule ne tue pas), mais si confiture il y a, vous l'étalez un peu partout sur le pain. Ensuite, en mordant dans la tartine, vous saurez avec quasi-certitude si elle était garnie ou pas.
L'idée est de se comporter avec une preuve comme avec une tartine : en étalant l'erreur pour la rendre décelable (par une transformation qui bien sûr conserve la qualité "sans erreur" si la démonstration est correcte).

P vs NP, graphes coloriables avec trois couleurs et théorème PCP

Dans la suite de l'exposé, il est question du fameux problème à 1 million de dollars P vs NP, du problème consistant à déterminer si un graphe est coloriable avec trois couleurs seulement, du lien entre les deux, et enfin du théorème PCP (qui dit en gros que tout problème de décision dans NP a des solutions vérifiables probabilistiquement) dont Irit Dinur a fourni une preuve combinatoire, et qui intervient dans des questions de robustesse ou d'approximation, aussi bien en combinatoire qu'en algèbre ou en analyse.
Il est impossible de commencer à raconter tout ceci sans être excessivement longue alors je dirai simplement que, là encore, la clarté de l'exposé est tel que tout semble couler de source, la synthèse des idées est très efficace et permet d'aborder une foule de choses en peu de temps, et surtout, l'enthousiasme de la conférencière est terriblement communicatif.

En conclusion, j'espère que cette jeune chercheuse enseigne (sinon, que d'étudiants perdus pour la cause !). J'espère aussi qu'elle obtiendra très vite un grand prix très prestigieux, qu'elle dégommera P vs NP ou que sais-je. Je n'ai évidemment pas la moindre compétence pour juger qui mérite un prix ou non. Si, en quittant l'auditorium, j'ose penser aux récompenses et à la médiatisation qui s'ensuit, c'est parce que je suis tellement ravie que je souhaite au monde entier d'avoir un jour la chance de voir une conférence d'Irit Dinur.

 

 

 

 

 

 

 

 

 

 

CIMG5965.JPG


 

 

 

 

 

CIMG5972.JPG