MacTutor

Biographie

Les parents de Leslie Valiant étaient Leslie Valiant et Eva Julia Ujlaki. Il a été élevé en Angleterre, fréquentant le lycée de Tynemouth, North Shields. Cette école a été renommée en 1969, plusieurs années après le départ de Valiant, lorsqu’elle est devenue connue sous le nom de Norham High School. Valiant a terminé ses études à la Latymer Upper School, à King Street, Hammersmith, à Londres. C’était (et c’est toujours) une célèbre école indépendante sélective avec une grande réputation remontant à sa fondation par Edward Latymer en 1624. Après avoir obtenu son diplôme de la Latymer Upper School, il a étudié au King’s College de Cambridge puis, après l’obtention de son premier diplôme, un BA en mathématiques, il est entré à l’Imperial College de Londres pour étudier l’informatique théorique. Après l’obtention du diplôme de l’Imperial College en informatique, Valiant est allé à l’Université de Warwick où il a entrepris des recherches pour un doctorat en informatique avec Michael Stewart Paterson comme conseiller.
Avant l’attribution de son doctorat., Valiant a passé l’année 1973-74 aux États-Unis en tant que professeur assistant invité à l’Université Carnegie Mellon de Pittsburgh, en Pennsylvanie. Il a reçu son doctorat de l’Université de Warwick en 1974 pour sa thèse Sur les procédures de décision pour les familles d’Automates de Poussée Déterministes. En collaboration avec son conseiller de thèse M S Paterson, Valiant avait présenté l’article sur les automates à un compteur déterministes à l’Erste Fachtagung der Gesellschaft für Informatik über Automatentheorie und Formale Sprachen Ⓣ à Bonn en 1973. Wilfried Brauer a examiné le document, écrivant:-

Un automate déterministe à un compteur (doca) est un automate de poussée déterministe ayant un alphabet de pile à un élément. Il est facile de voir que les problèmes d’inclusion et de nullité d’intersection pour les doca sont indécidables. En revanche, les auteurs donnent une procédure de décision pour l’équivalence des doca et montrent que sa complexité temporelle est limitée au-dessus par une fonction exponentielle dans environ la racine carrée du nombre d’états des doca testés. Ils conjecturent que l’équivalence est décidable pour la classe de tous les automates de poussée déterministes.

Valiant a publié l’article The equivalence problem for deterministic finite-turn pushdown automata en 1974. S A Greibach souligne l’importance de cet article: –

Un automate de magasin pushdown (pda) est à tour fini s’il existe une limite uniforme sur le nombre de fois où il peut passer de pushing (augmentant la longueur du magasin pushdown) à popping (diminuant la longueur du magasin pushdown) lors de tout calcul sur n’importe quelle entrée. L’auteur établit la décidabilité du problème d’équivalence (deux machines acceptent-elles le même langage ?) pour les pda à tour fini déterministes. L’importance du résultat réside dans les techniques de preuve utilisées pour l’établir et dans le fait qu’il représente l’une des avancées majeures pour résoudre la conjecture de longue date selon laquelle le problème d’équivalence pour les pda déterministes (dpda) est décidable (le problème correspondant est connu pour être indécidable pour les pda non déterministes même dans des cas très restreints).

Après son retour des États-Unis en 1974, Valiant a pris des cours à l’Université de Leeds où il a travaillé pendant les deux années 1974-76. Donnons un autre exemple de ses premiers articles, celui-ci encore écrit en collaboration avec M S Paterson,. Cet article de 1975 sur les automates déterministes à un compteur commence par l’introduction suivante des auteurs : –

Nous présentons une analyse des automates déterministes à un compteur afin de montrer que le problème d’équivalence pour eux est décidable. Tous nos arguments et résultats peuvent être traduits directement en termes théoriques de schéma. Le corollaire qui suit est que l’équivalence est décidable pour les schémas de Janov même lorsqu’on leur permet un compteur auxiliaire.

Valiant s’installe en Écosse en 1975 pour suivre des cours à l’Université d’Édimbourg. En 1977, il épouse Gayle Lynne Dyckhoff; ils ont deux fils Gregory John Valiant et Paul A Valiant. À Édimbourg, il a été promu lecteur en 1981, mais est allé aux États-Unis en 1982 alors qu’il était professeur invité à Harvard. Plus tard cette année-là, il a été nommé Professeur Gordon McKay d’Informatique et de Mathématiques appliquées à Harvard. Il est resté à Harvard, bien qu’il ait passé l’année 1987-88 en tant que chercheur invité à l’Université d’Oxford en Angleterre. En 2001, il a été nommé Professeur Jefferson Coolidge d’Informatique et de Mathématiques appliquées à la Harvard School of Engineering and Applied Sciences.
Les contributions de Valiant sont tout à fait remarquables et il a reçu les plus grands honneurs pour ses réalisations. Il a été boursier Guggenheim en 1985-86 et a reçu le prix Nevanlinna en 1986. Il a été élu membre de la Royal Society de Londres en 1991 et, l’année suivante, membre de l’American Association for Artificial Intelligence. Il a reçu le Prix Knuth du Groupe d’intérêt spécial de l’Association for Computing Machinery sur les Algorithmes et la Théorie du Calcul et du Comité Technique de l’Institut des Ingénieurs en Électricité et en Électronique sur les Fondements Mathématiques de l’Informatique en 1997. Il a été élu à l’Académie nationale des Sciences des États-Unis en 2001, a reçu le Prix de l’Association Européenne pour l’Informatique théorique et le Prix A M Turing 2010 de l’Association for Computing Machinery qui sera remis à Valiant lors du banquet annuel de remise des prix de l’Association à San Jose, en Californie, le 4 juin 2011. Le prix comprend également un prix en argent de 250 000 $.
Nous n’avons pas expliqué les contributions de Valiant qui lui ont valu les plus hautes récompenses possibles. Pour ce faire, nous citons le commentaire qui accompagne l’annonce du Prix Turing (les articles 2011 référencés ci-dessous citent ce commentaire). Le commentaire commence: –

Au cours des 30 dernières années, Leslie Valiant a apporté des contributions fondamentales à de nombreux aspects de l’informatique théorique. Son travail a ouvert de nouvelles frontières, introduit de nouveaux concepts ingénieux et présenté des résultats d’une grande originalité, profondeur et beauté. À maintes reprises, le travail de Valiant a littéralement défini ou transformé le paysage de la recherche en informatique.

Il continue ensuite à donner des détails sur plusieurs domaines auxquels Valiant a apporté des contributions étonnantes. Nous donnons quelques courts extraits de chacun des quatre domaines:

  1. Théorie de l’apprentissage computationnel. La plus grande contribution de Valiant peut être son article « A theory of the learnable » (1984), qui a jeté les bases de la théorie de l’apprentissage computationnel. … Le modèle « probablement approximativement correct » (PAC) de Valiant a fourni de belles bases pour le concept même d’apprentissage.
  2. Complexité de l’énumération. Au début des années 1970, la complexité de calcul traitait généralement de la difficulté des problèmes de décision, tels que si un graphique a une correspondance parfaite ou si un vendeur itinérant peut trouver un itinéraire d’au plus une certaine longueur. … L’une des découvertes les plus remarquables de Valiant est que les problèmes de comptage sont beaucoup plus subtils que l’expérience précédente ne le suggérait. Un problème de comptage demande le nombre de certains objets combinatoires: par exemple, combien de correspondances parfaites y a-t-il dans un graphique? Nous ne posons pas seulement le problème de la décision de savoir si ce nombre est positif, mais aussi de sa taille. Si le problème de décision est difficile, alors le problème de comptage doit l’être aussi, mais la réalisation surprenante de Valiant était que l’inverse échoue. Dans son article « The complexity of computing the permanent » (1979), il a montré que bien qu’il existe un algorithme efficace pour savoir si un graphe a une correspondance parfaite, il n’existe pas d’algorithme efficace pour compter les correspondances parfaites (à moins que P = NP), et en fait, compter les correspondances parfaites est aussi difficile que tout problème de comptage. Cela a été un choc pour la communauté de la complexité informatique, qui s’était habituée à l’idée que les problèmes de décision captureraient facilement les principales caractéristiques d’un problème.
  3. Calcul algébrique. Une autre contribution clé à la complexité informatique a été la théorie du calcul algébrique de Valiant, dans laquelle il a établi un cadre pour comprendre quelles formules algébriques peuvent être évaluées efficacement. … Dans son article « Complétude classes in algebra » (1979), Valiant a caractérisé la difficulté du calcul algébrique en termes de deux fonctions fondamentales et étroitement liées de l’algèbre linéaire, à savoir le déterminant et le permanent.
  4. Calcul parallèle et distribué. En plus de la théorie de l’apprentissage computationnel et de la complexité computationnelle, un troisième grand domaine dans lequel Valiant a apporté des contributions importantes est la théorie du calcul parallèle et distribué. Ses résultats ici vont des idées simples, mais puissantes et élégantes, au réexamen des fondements mêmes. Un exemple d’un aperçu simple est son schéma de routage parallèle, décrit dans l’article « A scheme for fast parallel communication » (1982).

Nous terminons cette biographie en citant en entier la conclusion de la citation du prix Turing: –

Rarement on voit une combinaison aussi frappante de profondeur et d’ampleur que dans l’œuvre de Valiant. Il est vraiment une figure héroïque de l’informatique théorique et un modèle pour son courage et sa créativité dans la résolution de certains des problèmes les plus profonds non résolus de la science.

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.