Un científico informático gana el premio Turing por su trabajo fundamental sobre la aleatoriedad

El científico computacional y matemático Avi Wigderson del Instituto de Estudios Avanzados (IAS) de Princeton ganó el Premio AM Turing 2023. El premio, que otorga anualmente la Association for Computing Machinery (ACM) a un científico informático por sus contribuciones en el campo, está dotado con un millón de dólares gracias a Google. Lleva el nombre del matemático británico Alan Turing, quien ayudó a desarrollar una base teórica para comprender la computación mecánica.

Wigderson está siendo honrado «por sus contribuciones fundamentales a la teoría de la computación, incluida la remodelación de nuestra comprensión del papel de la aleatoriedad en la computación y por sus décadas de liderazgo intelectual en la informática teórica». También ganó el prestigioso Premio Abel en 2021 por su trabajo en informática teórica, la primera persona en recibir este doble honor.

«Avi ha hecho contribuciones fundamentales a la teoría de la computación, desde algoritmos paralelos hasta la criptografía y absolutamente todos los aspectos de la teoría de la complejidad», dijo Shafi Goldwasser, director del Instituto Simons de Teoría de la Computación, quien ganó el Premio Turing 2012. «Sus numerosas contribuciones durante décadas a las áreas de desrandomización y pseudoaleatoridad nos han llevado a una comprensión profunda del profundo papel de la aleatoriedad en la informática».

Nacido en Haifa, Israel, Wigderson era hijo de un ingeniero eléctrico y una enfermera. Su padre le transmitió a su hijo su propio amor por la resolución de acertijos y las matemáticas. Wigderson estudió en el Technion (Instituto Israelí de Tecnología) y obtuvo su doctorado en informática en Princeton en 1983. Ocupó algunos puestos de corta duración antes de unirse a la facultad de la Universidad Hebrea tres años después. Ha trabajado en la IAS desde 1999 y es residente de tiempo completo desde 2003.

Si bien las computadoras son sistemas fundamentalmente deterministas, los investigadores descubrieron en la década de 1970 que podían enriquecer sus algoritmos permitiéndoles tomar decisiones aleatorias durante el cálculo con la esperanza de mejorar su eficiencia. Y funcionó. Era más fácil para los informáticos comenzar con una versión aleatoria de un algoritmo determinista y luego «desaleatorizarlo» para obtener un algoritmo que fuera determinista.

En 1994, Wigderson fue coautor de un artículo fundamental sobre dureza versus aleatoriedad con Noam Nisan, demostrando que, por muy útil que pueda ser, la aleatoriedad no es una necesidad. Esencialmente, «todo algoritmo probabilístico que sea eficiente puede ser reemplazado por uno determinista, por lo que realmente no es necesario [randomness]», dijo Wigderson a Ars. «El poder que se cree que tienen los algoritmos probabilísticos no existe». Posteriormente fue coautor de dos artículos más influyentes que amplían aún más ese trabajo sobre la aleatoriedad, entre muchos otros.

El libro de Wigderson de 2019, Matemáticas y Computación: Una Teoría que Revoluciona la Tecnología y la Ciencia, está disponible para descargar en su sitio web. «Un tema central es que la computación ocurre en todas partes, no sólo en las computadoras», dijo Wigderson. «Es parte de los procesos de nuestro cerebro, de la forma en que hablamos y de las células de nuestro cuerpo, pero también de los árboles que crecen o del clima y de las cosas celestes. En todos estos procesos naturales existen leyes de la naturaleza, que son locales, y evolucionan sistemas. Como en una computadora, hay reglas muy simples, y comienzas con un problema y descubres una solución compleja. Por lo tanto, la metodología es aplicable a esencialmente cualquier proceso o estudio científico. Hay colaboraciones fantásticas con estadísticos. física, con la física cuántica, con la biología computacional, con la economía, con las ciencias sociales: muchas conexiones hermosas y extremadamente fructíferas».

La propia investigación de Wigderson es puramente teórica. «No me motivan las solicitudes», afirmó. «Pero sé que en el trabajo fundamental encontramos usos. Piense en Alan Turing. Escribió un artículo matemático sobre lógica en una revista poco conocida sobre problema de entscheidung. No fue motivado por la solicitud. Pero esto es lo que inicia la informática. Él mismo reconoció que el modelo que estaba sugiriendo es tan simple que podemos empezar a construirlo».

Dicho esto, confiesa estar gratamente sorprendido por la eventual aplicación de su trabajo sobre pruebas interactivas de conocimiento cero a mediados de los años ochenta. Con Silvio Micali y Oded Goldreich, Wigderson amplió el trabajo anterior de Micali sobre pruebas interactivas a problemas NP, concluyendo que la solución a cada uno de esos problemas también se puede probar con una prueba de conocimiento cero.

«Básicamente, descubrimos que todo lo que se puede probar se puede probar sin revelar a la persona que verifica la prueba ningún conocimiento que no conocía», dijo Wigderson. «La motivación vino de la criptografía, donde quiero demostrarles que seleccioné mi clave secreta de la manera que requiere el protocolo, pero no quiero decirles cuál es mi clave secreta. El resultado es muy general, y si bien muy satisfactorio, fue una solución teórica que me pareció muy complicada de implementar, pero ahora variantes de la misma son parte de blockchains y otros sistemas criptográficos, por lo que a veces nos sorprende la diligencia de las personas que realmente se preocupan por la práctica y realmente quieren ver las cosas funcionando».

Wigderson sigue siendo tan curioso como siempre y está especialmente entusiasmado por poder colaborar con nuevos grupos de postdoctorados cada año. Un proyecto actual se refiere a la optimización convexa en entornos no euclidianos. La optimización convexa se ha aplicado ampliamente en el aprendizaje automático, el procesamiento de señales, la visión por computadora y los sistemas de control automático, por ejemplo. El proyecto de Wigderson busca «generalizar la teoría a variedades, a estructuras que aparecen en una gran variedad de áreas matemáticas y físicas: teoría de la información cuántica, teoría invariante y definitivamente en ciencias de la computación», dijo. «También aparece en análisis, para demostrar desigualdades y en álgebra para demostrar identidades. Es bastante amplio y estoy muy entusiasmado con él».