Die Laureaten

Copyright © Klaus Tschira Stiftung / Peter Badge

Leslie G. Valiant

geboren am 28. März 1949 in Budapest (Ungarn)

Turing-Award (2010) „für umwälzende Beiträge zur Theorie der Berechenbarkeit, darunter die Theorie des ‘wahrscheinlich annähernd richtigen Lernens’ (WARL), die Komplexität des Enumerierens und der algebraischen Berechenbarkeit sowie die Theorie des parallelen und verteilten Rechnens.”

Nevanlinna-Preis (1986) „für herausragende Arbeit in den mathematischen Bereichen der Informatik“.

Leslie Valiants Vater, ebenfalls Leslie genannt, war ein Chemie-Ingenieur und seine Mutter Eva eine Übersetzerin für mehrere Sprachen. Er erhielt seine höhere Erziehung in England, studierte am King’s College in Cambridge Mathematik (Bachelor of Arts 1970) und anschließend am Imperial College in London Informatik (Diploma des Imperial College). Valiant promovierte an der University of Warwick bei Michael Paterson (Ph.D. 1971-73) über „Decision Procedures for Families of Deterministic Pushdown Automata”. Er arbeitete dann für ein Jahr als Gastdozent an der Carnegie Mellon University in Pittsburgh, Pennsylvania (1973-1974). Anschließend lehrte er an der Leeds University (1974-1976) und der University of Edinburgh (1977-82). 1982 ging er an die Harvard University und übernahm dort den Gordon McKay Lehrstuhl für Informatik und angewandte Mathematik und wechselte 2001 auf den T. Jefferson Coolidge Lehrstuhl für Informatik und angewandte Mathematik. Er erhielt den Knuth Prize (1997) und den European Association for Theoretical Computer Science Award (2008).

Graphen sind mathematische Objekte, die man sich vorstellen kann wie Landkarten: Knoten (Städte) sind durch Kanten verbunden (Straßen). Die Straßen können auch über- oder untereinander weg führen. In Graphen kann man folgendes Spiel machen: Aufgabe ist, sich Straßen herauszupicken, aber so, dass in keine Stadt mehr als eine einzelne ausgewählte Straße mündet. Eine solche Auswahl nennt man ein „Matching”, und wenn in jede Stadt genau eine Straße aus der Auswahl führt, dann heißt das Matching perfekt. Ist ein Graph gegeben, so stellen sich sofort zwei Fragen bezüglich Matchings: Man kann fragen, ob ein perfektes Matching in dem Graph existiert und, falls ja, wie viele es gibt.

In den 1970er Jahren studierte Leslie Valiant Fragen der zweiten Art, nämlich solche, bei denen man die Anzahl der Lösungen für ein gegebenes Problem zählt. Valiant bewies die erstaunliche Tatsache, dass es zwar leicht ist, die Existenz eines perfekten Matchings zu zeigen, das Zählen der Matchings aber viel schwieriger ist (#P-vollständig) und in der Praxis für große Graphen womöglich sogar undurchführbar. Außerdem zeigte er, das diese Kluft zwischen der Einfachheit, die Existenz von Lösungen zu zeigen, und der Schwierigkeit, sie zu zählen, ein durchgängiges Phänomen ist, das überall in der Mathematik und Informatik auftaucht.

Berühmt wurde Leslie Valiant aber auch dafür, die Grundlagen für eine Theorie des Lernens gelegt zu haben, mit dem Aufsatz „A theory of the learnable” von 1984. In diesem Forschungsgebiet geht es um das alte Problem, wie man vom Sichten von Beispielen, die sich in verschiedene Kategorien sortieren lassen (wie beispielsweise Blumen, die nach Arten klassifiziert werden), eine Verallgemeinerung ableiten kann, mit der sich Beispiele, die man zuvor noch nicht gesehen hat, effektiv in Klassen einteilen lassen. Der Aufsatz beschreibt ein mathematisches Kriterium dafür, wann man Lernen als erfolgreich und rechnerisch zulässig ansehen kann. Von dieser grundlegenden Definition des Lernens lässt sich eine direkte Brücke zum Maschinenlernen schlagen. Valiant variierte die Theorie auch zu einer mathematischen Theorie des Spielraums und der Grenzen der biologischen Evolution.

1977 heiratete Leslie Gayle Dyckoff, eine Psychologin. Sie haben zwei Söhne, Paul und Gregory.