Leslie Valiant

Leslie Valiant 2005 in Oberwolfach

Leslie Gabriel Valiant (* 28. März 1949) ist ein britischer Informatiker und Turingpreisträger.

Studium und Forschung

Valiant studierte an der University of Cambridge (King’s College), am Imperial College London und an der University of Warwick, wo er 1974 in Informatik bei Michael Paterson promovierte (Decision Procedures for Families of Deterministic Pushdown Automata). Danach war er an der Carnegie Mellon University, der University of Leeds und der University of Edinburgh. Ab 1982 lehrte er an der Harvard University, wo er zur Zeit T. Jefferson Coolidge Professor für Informatik und Angewandte Mathematik ist.

Valiant beschäftigte sich besonders mit Komplexitätstheorie (Einführung von Sharp-P 1979), Computational learning theory (Einführung des PAC-Modells des Maschinenlernens: Probably Approximately Correct Learning), parallelem Rechnen, neuronalem Rechnen, Evolutions-Modellen und Künstlicher Intelligenz. Von ihm stammt das Konzept holographischer Algorithmen.

1985 bewies er mit Vijay Vazirani ein wichtiges Resultat der Komplexitätstheorie (Valiant-Vazirani-Theorem), dass wenn UNIQUE-SAT in P ist, die Komplexitätsklassen NP und RP (random polynomial) identisch sind.^[1]

Zu seinen Doktoranden zählt Mark Jerrum.

Auszeichnungen

1986 erhielt er den Nevanlinna-Preis, 1997 den Knuth-Preis für Informatik, 2008 den EATCS-Award und 2010 den Turing Award. Er ist Fellow der Royal Society und Mitglied der National Academy of Sciences.

Schriften

• Circuits of the mind. Oxford University Press, 1994, 2000

Einzelnachweise

1. ↑ Valiant, Vazirani NP is as easy as detecting unique solutions, Proceedings of the seventeenth annual ACM symposium on Theory of computing, 1985, S.458–463

Weblinks

• Homepage in Harvard (englisch)

PND: kein individualisierter Datensatz vorhanden (Stand: 12. Februar 2011)

Normdaten: LCCN: n91063548 | VIAF: 56713854 | WorldCat | WP-Personeninfo