Leslie Gabriel Valiant (nacido el 28 de marzo de 1949) es un informático y teórico computacional británico-estadounidense, actualmente profesor T. Jefferson Coolidge de Informática y Matemáticas Aplicadas en la Universidad de Harvard. Es más conocido por introducir el modelo de aprendizaje Probablemente Aproximadamente Correcto (PAC), que fundó el campo de la teoría del aprendizaje computacional y se convirtió en una base teórica para el aprendizaje automático. También introdujo el concepto de #P-completitud en teoría de la complejidad y el modelo Bulk Synchronous Parallel (BSP) para computación paralela. La Association for Computing Machinery le otorgó el Premio Turing A.M. de 2010, describiéndolo como una "figura heroica" en informática teórica por su "combinación notable de profundidad y amplitud" al abordar problemas profundos no resueltos en la ciencia.
Valiant nació de un padre ingeniero químico y una madre traductora. Cursó estudios superiores en el King's College de Cambridge, el Imperial College de Londres y la Universidad de Warwick, donde obtuvo un doctorado en informática en 1974. Antes de unirse a Harvard en 1982, ocupó cargos académicos en la Universidad de Edimburgo, la Universidad de Leeds y la Universidad Carnegie Mellon.
Teoría de la Complejidad y #P-Completitud
En 1977, Valiant introdujo la clase de complejidad #P (Sharp-P) para clasificar problemas de conteo y enumeración, como calcular el permanente de una matriz o contar emparejamientos en un grafo. Su trabajo estableció la #P-completitud como una noción fundamental en teoría de la complejidad, explicando por qué muchos problemas de fiabilidad y enumeración son computacionalmente intratables a pesar de ser problemas de decisión fáciles de verificar. Esta contribución reformuló cómo los teóricos entienden la dificultad de problemas más allá de simples tareas de decisión.
Aprendizaje PAC y Teoría del Aprendizaje Computacional
En 1984, Valiant definió un marco para el aprendizaje inductivo que combinaba la viabilidad computacional con la aplicabilidad a clases de reglas lógicas no triviales. Este marco, llamado posteriormente aprendizaje Probablemente Aproximadamente Correcto (PAC), formalizó cómo un aprendiz puede generalizar a partir de un número limitado de muestras mientras tolera una pequeña probabilidad de error. El aprendizaje PAC proporcionó una base teórica para el aprendizaje automático, abordando preguntas sobre la complejidad de muestras y la tratabilidad computacional. Su libro de 2013 Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World extendió estas ideas, argumentando que los algoritmos de aprendizaje sustentan no solo la computación sino también la evolución y la cognición. En el libro, sostuvo que la biología evolutiva carece de una explicación adecuada de la tasa de evolución y su capacidad para desarrollar mecanismos complejos bajo entornos cambiantes, a pesar de la corrección general del esquema de Darwin.
Educación y carrera temprana
Valiant estudió en el King's College de Cambridge y el Imperial College de Londres antes de completar un doctorado en informática en la Universidad de Warwick en 1974. Su trabajo temprano en teoría de autómatas produjo un algoritmo para el análisis sintáctico de gramáticas libres de contexto que sigue siendo el más rápido asintóticamente conocido. También pionó el uso de propiedades de grafos para analizar computaciones, vinculando la teoría estructural de grafos con la eficiencia algorítmica.
Contribuciones a la computación
La investigación de Valiant abarca múltiples áreas de la informática teórica. Introdujo la noción de #P-completitud para explicar por qué los problemas de enumeración y fiabilidad son intratables, siendo la primera aplicación la función del permanente de una matriz. En 1984 propuso el modelo de aprendizaje PAC, que proporcionó una definición rigurosa del aprendizaje a partir de ejemplos y se convirtió en una base para la inteligencia artificial. También desarrolló algoritmos holográficos, inspirados en la computación cuántica, e hizo contribuciones tempranas a la teoría de autómatas con un algoritmo de análisis sintáctico libre de contexto que sigue siendo el más rápido asintóticamente conocido. En la década de 1990, Valiant formuló el modelo Bulk Synchronous Parallel (BSP), análogo al modelo de von Neumann pero para arquitecturas paralelas; ha influido en sistemas como Pregel y Beam de Google, y en proyectos de código abierto como Hadoop y Spark.
Educación y carrera académica
Valiant estudió en el King's College de Cambridge, luego en el Imperial College de Londres, y recibió su doctorado en informática de la Universidad de Warwick en 1974. Enseñó en la Universidad de Edimburgo y luego en la Universidad Carnegie Mellon antes de unirse a la Universidad de Harvard en 1982, donde ha permanecido desde entonces. En Harvard, ha trabajado en informática teórica y neurociencia computacional, centrándose en comprender los procesos de memoria y aprendizaje.
Aprendizaje PAC y Aprendizaje Automático
La introducción del modelo PAC por Valiant en 1984 formalizó las condiciones bajo las cuales un aprendiz puede generalizar a partir de un conjunto finito de ejemplos. Este marco reconcilió la viabilidad computacional con el aprendizaje de reglas lógicas - se convirtió en una piedra angular de la teoría del aprendizaje computacional e influyó en el desarrollo de inteligencia artificial práctica. Su libro de 2013 Probably Approximately Correct extendió estas ideas a la biología y la evolución, argumentando que la teoría evolutiva actual no explica adecuadamente la tasa de progreso evolutivo y que la teoría del aprendizaje ofrece analogías útiles.
Computación paralela y distribuida
El modelo Bulk Synchronous Parallel de Valiant, introducido en 1990, proporciona un puente entre hardware y software para computación paralela al organizar la ejecución en superpasos con sincronización de barrera. El modelo influyó en sistemas de procesamiento distribuido como Pregel de Google y los proyectos de código abierto Apache Giraph, Apache Hama y Dask. Su trabajo temprano en Xerox PARC y contextos adyacentes sentaron las bases para motores de análisis de grafos escalables utilizados en centros de datos modernos.
Premios y honores
Valiant recibió el Premio Nevanlinna en 1986, el Premio Knuth en 1997, el Premio EATCS en 2008 y el Premio Turing A.M. en 2010. Fue elegido miembro de la Royal Society (FRS) en 1997 y miembro de la Academia Nacional de Ciencias de los Estados Unidos. Su citación del Premio Turing destacó sus contribuciones transformadoras a la teoría del aprendizaje PAC, la complejidad de la computación de conteo y algebraica, y la teoría de la computación paralela y distribuida.
Vida personal
Valiant está casado y tiene dos hijos, Gregory Valiant y Paul Valiant, ambos informáticos. Gregory trabaja en la Universidad de Stanford y Paul en complejidad computacional y criptografía. Valiant comparte su dedicación a la informática teórica con sus hijos, quienes contribuyen al campo en sus propias investigaciones.