Leslie Gabriel Valiant FRS [4] [5] (nacido el 28 de marzo de 1949) es un informático británico-estadounidense [6] y teórico computacional . [7] [8] Nació de un padre ingeniero químico y una madre traductora. [9] Actualmente es profesor T. Jefferson Coolidge de Ciencias de la Computación y Matemáticas Aplicadas en la Universidad de Harvard . [10] [11] [12] [13] Valiant recibió el Premio Turing en 2010, habiendo sido descrito por la ACM como una figura heroica en la informática teórica y un modelo a seguir por su coraje y creatividad al abordar algunos de los problemas más profundos sin resolver en la ciencia; en particular por su "sorprendente combinación de profundidad y amplitud". [6]
Valiant estudió en el King's College de Cambridge , [14] [6], el Imperial College de Londres , [14] [6] y la Universidad de Warwick , donde recibió un doctorado en informática en 1974. [15] [1]
Valiant es mundialmente conocido por su trabajo en Ciencias de la Computación Teórica . Entre sus muchas contribuciones a la Teoría de la Complejidad , introdujo la noción de #P-completitud ("Sharp-P completitud") para explicar por qué los problemas de enumeración y confiabilidad son intratables. Creó el modelo de aprendizaje Probablemente Aproximadamente Correcto o PAC que introdujo el campo de la Teoría del Aprendizaje Computacional y se convirtió en una base teórica para el desarrollo del Aprendizaje Automático . También introdujo el concepto de Algoritmos Holográficos inspirados en el modelo de Computación Cuántica . En sistemas informáticos, es más conocido por introducir el modelo de procesamiento paralelo sincrónico masivo . Análogo al modelo de von Neumann para una única arquitectura informática, BSP ha sido un modelo influyente para arquitecturas de computación paralela y distribuida. Ejemplos recientes son Google adoptándolo para computación a gran escala a través de MapReduce , MillWheel, [16] Pregel [17] y Dataflow , y Facebook creando un sistema de análisis de gráficos capaz de procesar más de 1 billón de aristas. [18] [19] También ha habido proyectos activos de código abierto para agregar programación BSP explícita, así como otros modelos de programación paralela de alto rendimiento derivados de BSP. Los ejemplos populares son Hadoop , Spark , Giraph , Hama , Beam y Dask . Su trabajo anterior en Teoría de Autómatas incluye un algoritmo para análisis sintáctico libre de contexto , que sigue siendo el asintóticamente más rápido conocido. También trabaja en Neurociencia Computacional centrándose en la comprensión de la memoria y el aprendizaje.
El libro de Valiant de 2013 se titula Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World (Probablemente aproximadamente correcto: los algoritmos de la naturaleza para aprender y prosperar en un mundo complejo ). [20] En él, sostiene, entre otras cosas, que la biología evolutiva no explica la velocidad a la que se produce la evolución, escribiendo, por ejemplo, "La evidencia de que el esquema general de Darwin para la evolución es esencialmente correcto es convincente para la gran mayoría de los biólogos. Este autor ha visitado suficientes museos de historia natural para convencerse él mismo. Todo esto, sin embargo, no significa que la teoría actual de la evolución sea adecuadamente explicativa. En la actualidad, la teoría de la evolución no puede ofrecer ninguna explicación de la velocidad a la que la evolución progresa para desarrollar mecanismos complejos o mantenerlos en entornos cambiantes".
Valiant comenzó a enseñar en la Universidad de Harvard en 1982 y actualmente es profesor T. Jefferson Coolidge de Ciencias de la Computación y Matemáticas Aplicadas en la Escuela de Ingeniería y Ciencias Aplicadas de Harvard . Antes de 1982, enseñó en la Universidad Carnegie Mellon , la Universidad de Leeds y la Universidad de Edimburgo .
Valiant recibió el Premio Nevanlinna en 1986, el Premio Knuth en 1997, el Premio EATCS en 2008, [21] y el Premio Turing en 2010. [22] [23] Fue elegido miembro de la Royal Society (FRS) en 1991, [4] miembro de la Asociación para el Avance de la Inteligencia Artificial (AAAI) en 1992, [24] y miembro de la Academia Nacional de Ciencias de los Estados Unidos en 2001. [25] La nominación de Valiant para la Royal Society dice:
Leslie Valiant ha contribuido de manera decisiva al crecimiento de la informática teórica. Su trabajo se centra principalmente en cuantificar matemáticamente los costes de recursos que supone resolver problemas en un ordenador. En un trabajo temprano (1975), encontró el algoritmo asintóticamente más rápido conocido para reconocer lenguajes libres de contexto. Al mismo tiempo, fue pionero en el uso de las propiedades de comunicación de los grafos para analizar los cálculos. En 1977, definió la noción de completitud "sharp-P" (#P) y estableció su utilidad para clasificar los problemas de recuento o enumeración según su manejabilidad computacional. La primera aplicación fue para contar emparejamientos (la función permanente de la matriz). En 1984, Leslie introdujo una definición de aprendizaje inductivo que, por primera vez, concilia la viabilidad computacional con la aplicabilidad a clases no triviales de reglas lógicas a aprender. Esta noción, más tarde denominada "aprendizaje probablemente aproximadamente correcto", se convirtió en una base teórica para el desarrollo del aprendizaje automático. En 1989, formuló el concepto de computación sincrónica masiva como principio unificador para la computación paralela. Leslie recibió el Premio Nevanlinna en 1986 y el Premio Turing en 2010. [26]
La mención que le cedió el premio AM Turing dice:
Por sus contribuciones transformadoras a la teoría de la computación, incluida la teoría del aprendizaje probablemente aproximadamente correcto (PAC), la complejidad de la enumeración y del cálculo algebraico, y la teoría de la computación paralela y distribuida. [6]
Sus dos hijos, Gregory Valiant [27] y Paul Valiant [28], también son científicos informáticos teóricos. [8]
Este artículo incorpora texto disponible bajo la licencia CC BY 4.0.