UREM-ULB :
Unité de Recherche sur l’Enseignement des Mathématiques

Irit Dinur est professeur d’informatique à l’Institut Weizmann. Sa recherche porte sur les fondements de l’informatique et la combinatoire, plus particulièrement sur les preuves vérifiables de manières probabiliste et sur la difficulté d’approximation.

I am a professor of computer science at the Weizmann Institute of Science. My research is in Foundations of Computer Science and in Combinatorics, especially Probabilistically Checkable Proofs, hardness of approximation.

« Epatante Irit Dinur

Evidemment, il faudrait demander ce qu’en pensent les vrais pros, mais cette prestation d’Irit Dinur est exactement ce que la non-mathématicienne que je suis aimerait voir tous les jours : des mathématiques enthousiasmantes, surprenantes, belles et admirablement racontées. L’entrée en matière est aussi comme je les aime : des questions abstraites et profondes, à la fois très mathématiques et très universelles. Le raisonnement fait intervenir des idées simples, presque enfantines, le genre d’idée dont on se dit : "Mais c’est bien sûr ! Comment n’y a-t-on pas pensé plus tôt ?" Voilà, à chaud et dans le désordre, mes sentiments en sortant de la conférence d’Irit Dinur (qui a, entre autres dons, une voix magnifique).
Bon, mais alors de quoi s’agit-il ?
Le titre de l’exposé est Probabillistically 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 ? ... Peut-être est-ce dû à l’art de l’oratrice, mais il me semble que l’on va au-delà des mathématiques pour toucher à la question du sens dans toute sa généralité.
Pour la suite, l’idée (on l’aura compris) 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. »

Source : Chroniques d’Hyderâbâd