MacTutor

Biografía

Los padres de Leslie Valiant fueron Leslie Valiant y Eva Julia Ujlaki. Se crió en Inglaterra, asistiendo a la escuela Secundaria Tynemouth, North Shields. Esta escuela fue renombrada en 1969, varios años después de que Valiant se fuera, cuando se conoció como Norham High School. Valiant completó su educación escolar en Latymer Upper School, en King Street, Hammersmith, Londres. Esta fue (y sigue siendo) una famosa escuela independiente selectiva con una gran reputación que se remonta a su fundación por Edward Latymer en 1624. Después de graduarse de Latymer Upper School, estudió en el King’s College de Cambridge y, después de obtener su primer título, una licenciatura en matemáticas, ingresó en el Imperial College de Londres para estudiar informática teórica. Después de la concesión del Diploma del Imperial College en Ciencias de la Computación, Valiant fue a la Universidad de Warwick, donde realizó investigaciones para un doctorado en ciencias de la computación con Michael Stewart Paterson como su asesor.
Antes de la concesión de su doctorado. Valiant pasó el año 1973-74 en los Estados Unidos como profesor Asistente Visitante en la Universidad Carnegie Mellon en Pittsburgh, Pensilvania. Fue galardonado con su doctorado por la Universidad de Warwick en 1974 por su tesis Procedimientos de Decisión para Familias de Autómatas Deterministas de Empuje. En colaboración con su asesor de tesis M S Paterson, Valiant había presentado el artículo Deterministic one-counter automata a la Erste Fachtagung der Gesellschaft für Informatik über Automatentheorie und Formale Sprachen Ⓣ en Bonn en 1973. Wilfried Brauer revisó el artículo, escribiendo:-

Un autómata determinista de un contador (doca) es un autómata determinista de empuje que tiene un alfabeto de pila de un elemento. Es fácil ver que los problemas de inclusión y nulidad de intersección para doca son indecidibles. En contraste con esto, los autores dan un procedimiento de decisión para la equivalencia de doca y mostrar que su tiempo de complejidad está acotada arriba por una función exponencial en aproximadamente la raíz cuadrada del número de estados de la prueba de la doca. Se conjetura que la equivalencia es de decidable para la clase de todos los deterministas pushdown autómatas.

Valiant publicó el artículo The equivalence problem for deterministic finite-turn pushdown automata en 1974. S A Greibach señala la importancia de este documento:-

Un autómata de almacén de pushdown (pda) es finito: gira si hay un límite uniforme en el número de veces que puede cambiar de empujar (aumentando la longitud del almacén de pushdown) a estallar (disminuyendo la longitud del almacén de pushdown) durante cualquier cálculo en cualquier entrada. El autor establece la decidibilidad del problema de equivalencia (¿aceptan dos máquinas el mismo lenguaje?) para pdas deterministas de giro finito. La importancia del resultado radica en las técnicas de prueba utilizadas para establecerlo y en el hecho de que representa uno de los principales avances hacia la solución de la conjetura pendiente de larga data de que el problema de equivalencia para pda deterministas (dpda) es decidible (se sabe que el problema correspondiente es indecidible para pda no deterministas, incluso en casos muy restringidos).

Después de regresar de los Estados Unidos en 1974, Valiant tomó una cátedra en la Universidad de Leeds, donde trabajó durante los dos años 1974-76. Vamos a dar otro ejemplo de sus primeros documentos, este escrito de nuevo en colaboración con M S Paterson,. Este artículo de 1975, autómatas deterministas de contador único, comienza con la introducción de los siguientes autores: –

Presentamos un análisis de autómatas deterministas de contador único con el fin de mostrar que el problema de equivalencia para ellos es decidible. Todos nuestros argumentos y resultados se pueden traducir directamente en términos teóricos de esquemas. El corolario que sigue es que la equivalencia es decidible para los esquemas de Janov incluso cuando se les permite un contador auxiliar.

Valiant se mudó a Escocia en 1975 para tomar clases en la Universidad de Edimburgo. En 1977 se casó con Gayle Lynne Dyckhoff; tuvieron dos hijos, Gregory John Valiant y Paul A Valiant. En Edimburgo fue ascendido a lector en 1981, pero se fue a los Estados Unidos en 1982 cuando era profesor visitante en Harvard. Más tarde ese año fue nombrado Profesor Gordon McKay de Ciencias de la Computación y Matemáticas Aplicadas en Harvard. Permaneció en Harvard, aunque pasó el año 1987-88 como miembro visitante en la Universidad de Oxford en Inglaterra. En 2001 fue nombrado 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.
Las contribuciones que ha hecho Valiant son bastante notables y ha recibido los más altos honores por sus logros. Fue Becario Guggenheim en 1985-86 y recibió el Premio Nevanlinna en 1986. Fue elegido miembro de la Royal Society de Londres en 1991 y, al año siguiente, miembro de la Asociación Americana de Inteligencia Artificial. Fue galardonado con el Premio Knuth de la Asociación de Maquinaria de Computación Grupo de Interés Especial en Algoritmos y Teoría de la Computación y el Instituto de Ingenieros Eléctricos y Electrónicos Comité Técnico sobre los Fundamentos Matemáticos de la Computación en 1997. Fue elegido miembro de la Academia Nacional de Ciencias de los Estados Unidos en 2001, recibió el Premio de la Asociación Europea de Ciencias Teóricas de la Computación y el Premio A Turing de la Asociación de Maquinaria Informática de 2010, que se entregará a Valiant en el banquete anual de premios de la Asociación en San José, California, el 4 de junio de 2011. El premio también incluye un premio en efectivo de $250,000.

No hemos explicado las contribuciones de Valiant que le han llevado a recibir los premios más altos posibles. Para hacer esto, citamos el comentario que acompaña al anuncio del Premio Turing (los artículos de 2011 a los que se hace referencia a continuación citan ese comentario). El comentario comienza: –

En los últimos 30 años, Leslie Valiant ha hecho contribuciones fundamentales a muchos aspectos de la informática teórica. Su obra ha abierto nuevas fronteras, introducido nuevos conceptos ingeniosos y presentado resultados de gran originalidad, profundidad y belleza. Una y otra vez, el trabajo de Valiant ha definido o transformado literalmente el panorama de la investigación en ciencias de la computación.

Luego continúa con los detalles de varias áreas a las que Valiant ha hecho contribuciones impresionantes. Damos algunos extractos cortos de cada una de las cuatro áreas:

  1. Teoría del aprendizaje computacional. La mayor contribución de Valiant puede ser su artículo’ A theory of the learnable ‘ (1984), que sentó las bases de la teoría del aprendizaje computacional. … El modelo «probablemente aproximadamente correcto» (PAC) de Valiant proporcionó hermosas bases para el concepto mismo de aprendizaje.
  2. Complejidad de la enumeración. A principios de la década de 1970, la complejidad computacional generalmente se ocupaba de la dificultad de los problemas de decisión, como si un gráfico tiene una coincidencia perfecta o si un vendedor ambulante puede encontrar una ruta de, como máximo, una cierta longitud. … Uno de los descubrimientos más notables de Valiant es que los problemas de conteo son mucho más sutiles de lo que la experiencia anterior sugirió. Un problema de conteo pide el número de algunos objetos combinatorios: por ejemplo, ¿cuántas coincidencias perfectas hay en un gráfico? No nos estamos limitando a plantear el problema de la decisión de si ese número es positivo, sino también de cuán grande es. Si el problema de la decisión es difícil, entonces el problema del conteo también debe serlo, pero la sorprendente comprensión de Valiant fue que lo contrario falla. En su artículo «The complexity of computing the permanent» (1979), mostró que aunque hay un algoritmo eficiente para saber si un gráfico tiene una coincidencia perfecta, no hay un algoritmo eficiente para contar coincidencias perfectas (a menos que P = NP), y de hecho contar coincidencias perfectas es tan difícil como cualquier problema de conteo. Esto fue un shock para la comunidad de complejidad computacional, que se había acostumbrado a la idea de que los problemas de decisión capturarían fácilmente las características clave de un problema.
  3. Cálculo algebraico. Otra contribución clave a la complejidad computacional fue la teoría de la computación algebraica de Valiant, en la que estableció un marco para comprender qué fórmulas algebraicas se pueden evaluar de manera eficiente. … En su artículo «Clases de completitud en álgebra» (1979), Valiant caracterizó la dificultad de la computación algebraica en términos de dos funciones fundamentales y estrechamente relacionadas del álgebra lineal, a saber, la determinante y la permanente.
  4. Computación paralela y distribuida. Además de la teoría del aprendizaje computacional y la complejidad computacional, una tercera área amplia en la que Valiant ha hecho contribuciones importantes es la teoría de la computación paralela y distribuida. Sus resultados aquí van desde ideas simples, pero poderosas y elegantes, hasta reexaminar los cimientos mismos. Un ejemplo de una visión simple es su esquema de enrutamiento paralelo, descrito en el documento» A scheme for fast parallel communication » (1982).

Terminamos esta biografía citando en su totalidad la conclusión de la cita del Premio Turing:-

Rara vez se ve una combinación tan sorprendente de profundidad y amplitud como en la obra de Valiant. Es verdaderamente una figura heroica en la informática teórica y un modelo a seguir por su coraje y creatividad para abordar algunos de los problemas más profundos sin resolver de la ciencia.

Deja una respuesta

Tu dirección de correo electrónico no será publicada.