Avi Wigderson (em hebraico: אבי ויגדרזון; nascido em 9 de setembro de 1956) é um cientista da computação e matemático israelense. Ele é o Professor Herbert H. Maass na escola de matemática do Instituto de Estudos Avançados em Princeton, Nova Jersey, Estados Unidos. Seus interesses de pesquisa incluem teoria da complexidade computacional, algoritmos paralelos, teoria dos grafos, criptografia e computação distribuída. Wigderson recebeu o Prêmio Abel em 2021 e o Prêmio Turing em 2023 por seu trabalho transformador em ciência da computação teórica.
O trabalho de Wigderson centra-se no papel da aleatoriedade na computação e na estrutura de algoritmos eficientes. Ele é uma figura de destaque na teoria da complexidade, tendo feito contribuições fundamentais para a compreensão do poder dos algoritmos aleatórios, a construção de grafos expansores via o produto zig-zag e os fundamentos das provas de conhecimento zero.
Início da vida e educação
Wigderson nasceu em Haifa, Israel, em 9 de setembro de 1956, filho de sobreviventes do Holocausto. Ele frequentou a Escola Hebraica Reali em Haifa. Em 1977, começou seus estudos de graduação no Technion - Instituto de Tecnologia de Israel, onde se formou em 1980. No Technion, conheceu sua esposa, Edna. Posteriormente, ele realizou estudos de pós-graduação na Universidade de Princeton, obtendo um Ph.D. em ciência da computação em 1983. Sua dissertação de doutorado, intitulada "Estudos em Complexidade Computacional", foi supervisionada por Richard Lipton. Wigderson é creditado por enriquecer vastamente o campo da complexidade computacional.
Carreira acadêmica
Após ocupar posições de curto prazo na Universidade da Califórnia, Berkeley, no Centro de Pesquisa IBM Almaden em San Jose, Califórnia, e no Instituto de Ciências Matemáticas em Berkeley, Wigderson retornou a Israel em 1986 para ingressar no corpo docente da Universidade Hebraica de Jerusalém. Ele recebeu estabilidade em 1987 e tornou-se professor titular em 1991. Em 1999, também assumiu uma posição no Instituto de Estudos Avançados e, em 2003, renunciou à sua posição na Universidade Hebraica para assumir o papel de Professor Herbert H. Maass no Instituto em Princeton.
No Instituto de Estudos Avançados, Wigderson tem se concentrado na interação entre complexidade computacional, matemática e criptografia. Ele ajudou a liderar uma geração de pesquisadores nessas áreas.
Principais contribuições
Wigderson investigou a questão fundamental de se a aleatoriedade é necessária para a computação eficiente. Com Noam Nisan e Russell Impagliazzo, Wigderson mostrou que, para certos algoritmos que dependem de lançamentos de moedas aleatórios, existe um algoritmo determinístico quase tão rápido que não usa aleatoriedade, desde que certas condições sejam satisfeitas. Esta linha de pesquisa, construída sobre o conceito de pseudorandomness, é uma pedra angular da ciência da computação teórica.
Trabalhando com Omer Reingold e Salil Vadhan, Wigderson desenvolveu o produto zig-zag, uma operação combinatória em grafos que combina grafos menores para produzir grafos maiores e bem conectados. Este conceito conecta a complexidade teórica, a teoria dos grafos e a teoria dos grupos, com aplicações que vão desde entender como navegar em um labirinto até construir grafos expansores eficientes. O produto zig-zag tornou-se uma ferramenta importante na ciência da computação teórica.
Wigderson, juntamente com Silvio Micali e Oded Goldreich, demonstrou que provas de conhecimento zero podem ser usadas para verificar resultados públicos sobre dados secretos sem revelar os segredos subjacentes. Este trabalho é uma camada fundamental para a criptografia moderna.
Prêmios e honrarias
Wigderson recebeu o Prêmio Nevanlinna em 1994, um prêmio da União Matemática Internacional, por seu trabalho em complexidade computacional. Em 2009, ele compartilhou o Prêmio Gödel pela construção zig-zag de grafos. Ele foi eleito para a Academia Americana de Artes e Ciências em 2011 e como Membro da ACM em 2018 por contribuições à ciência da computação teórica e à matemática.
Em 2019, Wigderson ganhou o Prêmio Knuth por, entre outras coisas, trabalho em computação aleatória, complexidade de circuitos, complexidade de provas e computação paralela. Ele recebeu o Prêmio Abel em 2021 com László Lovász por contribuições fundamentais à ciência da computação teórica e à matemática discreta. Em abril de 2024, a Associação para Maquinaria de Computação concedeu-lhe o Prêmio Turing por reformular a compreensão da aleatoriedade na computação e por décadas de liderança em ciência da computação teórica. Ele também recebeu o Prêmio Grande Imigrante da Carnegie Corporation em 2025.
Vida pessoal
Wigderson é casado com Edna, e eles têm um filho, Yuval, que é professor de matemática no Instituto de Ciência e Tecnologia da Áustria. Wigderson continua a inspirar novos pesquisadores através de seu trabalho e orientação.