Leslie Valiant

informática teórica del Reino Unido

Leslie Gabriel Valiant (nacido el 28 de marzo de 1949) es un informático teórico británico.

Leslie Valiant

Educado en el King's College, Cambridge, Imperial College London y la Universidad de Warwick donde recibió su Ph.D. en ciencias de computación en 1974. Comenzó dictando clases en la Universidad de Harvard en 1982 y actualmente es un T. Jefferson Coolidge Professor de Ciencias de Computación y Matemáticas Aplicadas en el Harvard School of Engineering and Applied Sciences. Antes de 1982 enseñó además en la Universidad Carnegie Mellon, en la Universidad de Leeds, y en la Universidad de Edimburgo. En 2010 Valiant recibe el Premio Turing.

Valiant es reconocido mundialmente por su trabajo en ciencias de la computación. Entre sus principales contribuciones a la complejidad computacional, se encuentra su introducción de la notación de Numeral-P-completo para explicar por qué los problemas de enumeración son intratables. También introdujo el modelo de machine learning PAC, que ayudó al desarrollo de esta teoría, y el concepto de algoritmos holográficos. Leslie Valiant también trabaja en neurociencia computacional, particularmente en la comprensión de la memoria y el aprendizaje.

Recibió el Premio Nevanlinna en 1986, el Premio Knuth en 1997, y el premio otorgado por la EATCS en 2008. Es miembro de la Royal Society de Londres, de la American Association for Artificial Intelligence, y de la Academia Nacional de Ciencias de Estados Unidos.

Uno de sus artículos más significativos, escrito junto con Vijay Vazirani, demuestra que si UNIQUE-SATP, entonces se cumple que NP = RP.

Valiant recibió el Premio Turing de la ACM "por sus transformadoras contribuciones a la teoría de la computación, incluyendo la teoría del aprendizaje probable, aproximadamente correcto, la complejidad de la enumeración y de la computación algebraica, y teorías de la computación paralela y distribuida."

Enlaces externosEditar