Leslie Valiant

Leslie Gabriel Valiant (Boedapest, 28 maart 1949) is een Brits informaticus. Hij werkt voornamelijk in de complexiteitstheorie, in de computationele leertheorie, en op het gebied van parallelle en gedistribueerde berekeningen. Voor zijn bijdragen in deze gebieden kreeg hij in 2010 de Turing Award.

Loopbaan

Leslie Valiant haalde zijn bachelordiploma in de wiskunde aan de King's College in Cambridge. Daarna studeerde hij aan Imperial College in Londen, om in 1974 aan de Universiteit van Warwick te promoveren.

Na op verschillende universiteiten in Groot-Brittannië gewerkt te hebben, is hij sinds 1982 hoogleraar in informatica en toegepaste wiskunde aan de Harvard-universiteit.

Wetenschappelijke bijdragen

Valiants wetenschappelijke werk bevindt zich voornamelijk in drie gebieden:

Complexiteitstheorie. Valiant definieerde de complextiteitsklasse #P, een complexiteitsklasse van functionele problemen die analoog is aan de complexiteitsklasse NP bij beslissingsproblemen.
Computationele leertheorie. Valiant introduceerde het probably approximately correct-model (PAC-model) om algoritmes voor machinaal leren te analyseren.
Parallel en gedistribueerd rekenen. Valiant ontwikkelde het buld synchronous parallel-model voor parallel algoritmes.

Onderscheidingen

Voor zijn werk ontving Valiant verschillende wetenschappelijke prijzen, waaronder de Nevanlinnaprijs (1986), de Knuthprijs (1997), de EATCS Award (2008) en de Turing Award (2010). Sinds 1991 is hij fellow van de Royal Society.