Prêmio Turing da ACM de 2023 é concedido ao professor Avi Wigderson

• A ciência da computação teórica trata dos fundamentos matemáticos da computação. Ela levanta questões como: "Este problema pode ser resolvido por meio da computação?" e "Se este problema pode ser resolvido pela computação, quanto tempo e quantos recursos são necessários?". Também investiga formas de projetar algoritmos eficientes. Toda tecnologia de computação que afeta nossas vidas é possibilitada por algoritmos. Entender os princípios de algoritmos poderosos e eficientes aprofunda não apenas a ciência da computação, mas também nossa compreensão das leis da natureza. A ciência da computação teórica é conhecida por apresentar desafios intelectuais fascinantes e, muitas vezes, não parece estar diretamente ligada à melhoria de aplicações práticas da computação, mas as inovações de pesquisa dessa área levam a avanços em quase todos os campos, como criptografia, biologia computacional, projeto de redes, aprendizado de máquina e computação quântica.

• Em essência, computadores são sistemas determinísticos. Quando um conjunto de instruções de um algoritmo é aplicado a uma determinada entrada, a computação é unicamente determinada e, em particular, a saída também é determinada. Ou seja, algoritmos determinísticos seguem padrões previsíveis. Em contraste, a aleatoriedade é a ausência de um padrão bem definido ou de previsibilidade de eventos/resultados. Como o mundo em que vivemos parece estar cheio de eventos aleatórios (como sistemas climáticos e fenômenos biológicos/quânticos), cientistas da computação vêm reforçando algoritmos para que possam fazer escolhas aleatórias durante o processo computacional, a fim de aumentar sua eficiência. De fato, muitos problemas para os quais não se conhecem algoritmos determinísticos eficientes foram resolvidos de forma eficiente por algoritmos probabilísticos (embora com uma pequena probabilidade de erro, que pode ser reduzida de forma eficiente). No entanto, a aleatoriedade é essencial ou pode ser eliminada? Qual é a qualidade de aleatoriedade necessária para o sucesso de algoritmos probabilísticos?

• O Dr. Avi Wigderson lidera a pesquisa em ciência da computação teórica há 40 anos e fez contribuições fundamentais para a compreensão do papel da aleatoriedade e da pseudorrandomicidade na computação. Cientistas da computação descobriram uma conexão notável entre aleatoriedade e dificuldade computacional (a identificação de problemas naturais para os quais não existem algoritmos eficientes). O Dr. Wigderson, junto de seus colegas, conduziu uma série extremamente influente de trabalhos sobre trocar dificuldade por aleatoriedade. Eles provaram que, sob hipóteses computacionais padrão e amplamente aceitas, todo algoritmo probabilístico em tempo polinomial pode eliminar a aleatoriedade de forma eficiente (ou seja, pode se tornar totalmente determinístico). Em outras palavras, a aleatoriedade não é essencial para a computação eficiente. Essa série de trabalhos revolucionou nossa compreensão do papel da aleatoriedade na computação e a forma como pensamos sobre aleatoriedade.

Contribuições do Dr. Wigderson

• "Hardness vs. Randomness" (coautoria com Noam Nisan): este artigo introduziu, entre outras coisas, um novo tipo de gerador pseudorrandômico e provou que a simulação determinística eficiente de algoritmos aleatorizados é possível sob hipóteses muito mais fracas do que se conhecia anteriormente.

• "BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs" (coautoria com László Babai, Lance Fortnow e Noam Nisan): este artigo demonstrou, usando "hardness amplification", que bounded-error probabilistic polynomial time (BPP) pode ser simulado em tempo subexponencial para infinitos comprimentos de entrada sob hipóteses mais fracas.

• "P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma" (coautoria com Russell Impagliazzo): este artigo apresentou geradores pseudorrandômicos mais fortes, com um tradeoff entre dificuldade e aleatoriedade essencialmente ótimo.

• Além de suas pesquisas relacionadas à aleatoriedade, o Dr. Wigderson também exerceu liderança intelectual em vários outros campos da ciência da computação teórica, incluindo provas interativas com múltiplos provadores, criptografia e complexidade de circuitos.

Opinião do GN⁺

• Do ponto de vista matemático, a pesquisa de Wigderson, que demonstrou a relação entre aleatoriedade e complexidade computacional, tem grande significado no contexto da interseção entre ciência da computação e matemática. Em particular, demonstrar que muitos algoritmos que dependiam de aleatoriedade podem, na verdade, ser implementados da mesma forma de maneira determinística é visto como algo que abriu um novo horizonte para a ciência da computação.

• Além disso, abordar matematicamente a relação entre eficiência e dificuldade também parece se tornar um tema importante de pesquisa em ciência da computação teórica. A possibilidade de que, quanto mais difícil for um problema, maior seja proporcionalmente a chance de existirem algoritmos mais eficientes para ele é uma percepção contraintuitiva.

• Por outro lado, o fato de o professor Wigderson ter enfatizado a integração entre matemática e ciência da computação para o avanço da ciência da computação teórica, além de ter se dedicado à formação de novas gerações de pesquisadores, parece ser um excelente exemplo para os sucessores da área acadêmica. Em especial, sua trajetória de ter recebido tanto o Prêmio Abel da matemática quanto o Prêmio Turing da ciência da computação pode ser vista como um caso simbólico que mostra a importância da ciência da computação teórica.

[GN⁺]

Comentários do Hacker News

• Avi Wigderson recebeu o ACM A.M. Turing Award de 2023. O prêmio reconhece suas contribuições fundamentais para a teoria da computação, especialmente por reformular a compreensão do papel da aleatoriedade na computação e por exercer liderança intelectual por décadas na área de ciência da computação teórica.

• Wigderson foi uma figura de liderança em áreas como teoria da complexidade computacional, algoritmos e otimização, aleatoriedade e criptografia, computação paralela e distribuída, combinatória e teoria dos grafos, além de atuar como elo entre a ciência da computação teórica, a matemática e a ciência em geral.

• Uma das principais realizações de Wigderson foi descobrir a surpreendente conexão entre aleatoriedade e dificuldade computacional. Sua pesquisa mostrou que a aleatoriedade não é necessariamente essencial para a computação eficiente.

• Em 2021, ele também recebeu o Prêmio Abel, tornando-se uma figura singular por conquistar as maiores honrarias tanto da matemática teórica/abstrata quanto da ciência da computação.

• Seu livro "Mathematics and Computation" foi publicado recentemente e vem recebendo elogios.

• Segundo seus resultados de pesquisa, se uma proposição pode ser provada, então uma prova de conhecimento zero (zero-knowledge proof) também é possível; além disso, ao aplicar números pseudoaleatórios a algoritmos probabilísticos, é possível obter algoritmos determinísticos eficientes para o mesmo problema. Isso sugere que a complexidade de modelos de computação probabilísticos, como os usados em IA, pode ser reduzida de forma significativa.