Científico computacional y matemático. Avi Wigderson del Instituto de Estudios Avanzados (IAS) de la Universidad de Princeton ganado oh 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 (esencialmente el Premio Nobel de Matemáticas) en 2021 por su trabajo en informática teórica: la primera persona en recibir un doble honor.
«Avi ha hecho contribuciones fundamentales a la teoría de la computación, desde algoritmos paralelos hasta criptografía, pasando por absolutamente todos los aspectos de la teoría de la complejidad», dijo Shafi Goldwasserdirector del Instituto Simons de Teoría de la Computación, que ganó el Premio Turing 2012. «Sus numerosas contribuciones durante décadas en las áreas de desrandomización y pseudoaleatoriedad nos han llevado a una profunda comprensión 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 amor por resolver 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 incorporarse a la facultad de la Universidad Hebrea tres años después. El ha estado con la IAS desde 1999 y residente a tiempo completo desde 2003.
Andrea Kane/Instituto de Estudios Avanzados
Aunque 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 “desaleatorizarla” para obtener un algoritmo determinista.
En 1994, Wigderson fue coautor de un papa seminalr sobre dureza versus aleatoriedad con Noam Nisan, demostrando que por más útil que pueda ser la aleatoriedad, no es una necesidad. Esencialmente, «Todo algoritmo probabilístico eficiente puede ser reemplazado por uno determinista, por lo que realmente no es necesario [randomness]», dijo. «El poder que se cree que tienen los algoritmos probabilísticos no existe». Más tarde fue coautor de dos más Muy influyente artículos que amplían aún más este trabajo sobre la aleatoriedad, entre muchos otros.
El libro de Wigderson de 2019, Matemáticas e informática: 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 informática ocurre en todas partes, no sólo en las computadoras», dijo Wigderson a Ars. «Es parte de los procesos en nuestro cerebro, en la forma en que podemos hablar y en las células de nuestro cuerpo, pero también en el crecimiento de los árboles o en el clima y las cosas celestiales. En todos estos procesos naturales, hay leyes de la naturaleza, que son locales y desarrollan sistemas. Como en una computadora, hay reglas muy simples, y comienzas con un problema y encuentras una solución compleja para él. Por lo tanto, la metodología es aplicable esencialmente a cualquier proceso o estudio científico. Hay Fantásticas colaboraciones con la física estadística, 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», dijo. «Pero sé que hemos encontrado usos para este trabajo fundamental. Piense en Alan Turing. Escribió un artículo matemático sobre lógica en una revista oscura sobre Problema de decisión. No fue motivado por la solicitud. Pero esto es lo que inicia la informática. Él mismo reconoció que el modelo que sugirió era tan simple que simplemente podíamos empezar a construirlo».
Dicho esto, confiesa estar gratamente sorprendido por la eventual aplicación de su trabajo en pruebas interactivas de conocimiento cero a mediados de la década de 1980. Con Silvio Micali y Oded Goldreich, Wigderson amplió el trabajo anterior de Micali sobre pruebas interactivas para problemas NP, concluyendo que la solución a cada uno de estos problemas también se puede probar con una prueba de conocimiento cero.
«Básicamente, encontramos que cualquier cosa que pueda ser probada, puede ser probada, sin revelar a la persona que verifica la prueba ningún conocimiento que no tuviera», dijo Wigderson. “La motivación vino de la criptografía, donde quiero demostrarles que seleccioné mi clave secreta en la forma que requiere el protocolo, pero no quiero decirles cuál es mi clave secreta. satisfactoria, era una solución teórica que parecía muy complicada de implementar. Pero ahora sus variantes forman parte de blockchains y otros sistemas criptográficos. Por eso, a veces nos sorprende la diligencia de las personas que realmente se preocupan por la práctica y realmente quieren que las cosas funcionen».
Wigderson sigue tan curioso como siempre y está especialmente entusiasmado por poder colaborar con nuevos grupos de posdoctorados cada año. Un proyecto actual se refiere optimizacion 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 amplia variedad de áreas de las matemáticas y la física: teoría de la información cuántica, teoría invariante y definitivamente en ciencias de la computación», dijo. «También aparece en el análisis, para probar desigualdades, y en álgebra, para probar identidades. Es bastante amplio y estoy muy entusiasmado con ello”.
