Avi Wigderson (en hebreo: אבי ויגדרזון; nacido el 9 de septiembre de 1956) es un informático teórico y matemático israelí. Es profesor Herbert H. Maass en la escuela de matemáticas del Instituto de Estudios Avanzados en Princeton, Nueva Jersey, Estados Unidos. Sus intereses de investigación incluyen la teoría de la complejidad computacional, algoritmos paralelos, teoría de grafos, criptografía y computación distribuida. Wigderson recibió el Premio Abel en 2021 y el Premio Turing en 2023 por su trabajo transformador en la informática teórica.
El trabajo de Wigderson se centra en el papel del azar en la computación y la estructura de los algoritmos eficientes. Es una figura destacada en la teoría de la complejidad, habiendo realizado contribuciones fundamentales para comprender el poder de los algoritmos aleatorios, la construcción de grafos expansores mediante el producto en zigzag y los fundamentos de las pruebas de conocimiento cero.
Primeros años y educación
Wigderson nació en Haifa, Israel, el 9 de septiembre de 1956, hijo de sobrevivientes del Holocausto. Asistió a la Escuela Hebrea Reali en Haifa. En 1977, comenzó sus estudios de pregrado en el Technion - Instituto Tecnológico de Israel, donde se graduó en 1980. En el Technion, conoció a su esposa, Edna. Posteriormente, realizó estudios de posgrado en la Universidad de Princeton, obteniendo un doctorado en informática en 1983. Su tesis doctoral, titulada "Studies in Computational Complexity" (Estudios sobre la complejidad computacional), fue supervisada por Richard Lipton. Se le atribuye a Wigderson haber enriquecido enormemente el campo de la complejidad computacional.
Carrera académica
Después de ocupar puestos temporales en la Universidad de California, Berkeley, en el Centro de Investigación IBM Almaden en San José, California, y en el Instituto de Ciencias Matemáticas de Berkeley, Wigderson regresó a Israel en 1986 para unirse al cuerpo docente de la Universidad Hebrea de Jerusalén. Obtuvo la titularidad (tenure) en 1987 y se convirtió en profesor titular en 1991. En 1999, también aceptó un puesto en el Instituto de Estudios Avanzados, y en 2003 renunció a su puesto en la Universidad Hebrea para asumir el rol de profesor Herbert H. Maass en el Instituto de Estudios Avanzados de Princeton.
En el Instituto de Estudios Avanzados, Wigderson se ha centrado en la interacción entre la complejidad computacional, las matemáticas y la criptografía. Ha ayudado a liderar a una generación de investigadores en estas áreas.
Contribuciones clave
Wigderson investigó la cuestión fundamental de si el azar es necesario para la computación eficiente. Con Noam Nisan y Russell Impagliazzo, Wigderson demostró que para ciertos algoritmos que dependen de lanzamientos de moneda aleatorios, existe un algoritmo determinista casi tan rápido que no utiliza aleatoriedad, siempre que se cumplan ciertas condiciones. Esta línea de investigación, basada en el concepto de pseudoaleatoriedad, es una piedra angular de la informática teórica.
Trabajando con Omer Reingold y Salil Vadhan, Wigderson desarrolló el producto en zigzag, una operación combinatoria sobre grafos que combina grafos más pequeños para producir otros más grandes y bien conectados. Este concepto une la teoría de la complejidad, la teoría de grafos y la teoría de grupos, con aplicaciones que van desde la comprensión de cómo navegar en un laberinto hasta la construcción de grafos expansores eficientes. El producto en zigzag se convirtió en una herramienta importante en la informática teórica.
Wigderson, junto con Silvio Micali y Oded Goldreich, demostró que las pruebas de conocimiento cero pueden utilizarse para verificar resultados públicos sobre datos secretos sin revelar los secretos subyacentes. Este trabajo es una capa fundamental para la criptografía moderna.
Premios y honores
Wigderson recibió el Premio Nevanlinna en 1994, un premio de la Unión Matemática Internacional, por su trabajo en complejidad computacional. En 2009, compartió el Premio Gödel por la construcción de grafos en zigzag. Fue elegido miembro de la Academia Estadounidense de las Artes y las Ciencias en 2011 y como miembro de la ACM en 2018 por sus contribuciones a la informática teórica y las matemáticas.
En 2019, Wigderson ganó el Premio Knuth por, entre otras cosas, su trabajo en computación aleatoria, complejidad de circuitos, complejidad de pruebas y computación paralela. Recibió el Premio Abel en 2021 junto con László Lovász por sus contribuciones fundamentales a la informática teórica y las matemáticas discretas. En abril de 2024, la Asociación de Maquinaria Computacional (ACM) le otorgó el Premio Turing por remodelar la comprensión del papel del azar en la computación y por décadas de liderazgo en la informática teórica. También recibió el Premio al Gran Inmigrante de la Corporación Carnegie de Nueva York en 2025.
Vida personal
Wigderson está casado con Edna, y tienen un hijo, Yuval, que es profesor de matemáticas en el Instituto de Ciencia y Tecnología de Austria. Wigderson continúa inspirando a los investigadores a través de su trabajo y su mentoría.