O prolífico pesquisador encontrou conexões profundas entre aleatoriedade e computação e passou uma carreira influenciando criptógrafos, pesquisadores de complexidade e muito mais.
Ele encontrou um campo rico em questões profundas e sem resposta, que eram, no fundo, matemáticas.
Um dos seus primeiros esforços inovadores centrou-se numa aparente contradição: se era possível convencer alguém de que uma afirmação matemática tinha sido provada sem mostrar como.
“A pessoa que vê a prova não aprende nada sobre a prova em si”, disse Ran Raz, cientista da computação da Universidade de Princeton.
Em 1985, Shafi Goldwasser, Silvio Micali e Charles Rackoff introduziram este conceito de provas interativas de conhecimento zero, demonstrando seu uso para algumas declarações.
Wigderson, juntamente com Micali e Oded Goldreich, mais tarde expôs essa ideia, expondo as condições que mostram que se uma afirmação pode ser provada, ela também tem uma prova de conhecimento zero.
“Este é um resultado importante em criptografia; é extremamente central”, disse Raz.
Usando uma prova de conhecimento zero, alguém pode provar que criptografou ou assinou corretamente uma mensagem usando sua chave secreta, sem revelar qualquer informação sobre ela.
“Avi tem alguns resultados extremamente importantes em criptografia, e este pode ser o mais importante deles.” Mas talvez o resultado mais fundamental de Wigderson esteja em outra área: vincular a dureza computacional à aleatoriedade.
No final da década de 1970, os cientistas da computação perceberam que, para muitos problemas difíceis, os algoritmos que empregavam a aleatoriedade, também chamados de algoritmos probabilísticos, poderiam superar amplamente as alternativas determinísticas.
Numa prova de 1977, por exemplo, Robert Solovay e Volker Strassen introduziram um algoritmo aleatório que poderia determinar se um número é primo mais rapidamente do que os melhores algoritmos determinísticos da época.
Para alguns problemas, algoritmos probabilísticos podem apontar para problemas determinísticos.
No início da década de 1980, Wigderson trabalhou com Richard Karp, da Universidade da Califórnia, Berkeley, para conectar a ideia de aleatoriedade a problemas considerados computacionalmente difíceis, o que significa que nenhum algoritmo determinístico conhecido pode resolvê-los em um período de tempo razoável.
“Não sabemos como provar que eles são difíceis”, disse Wigderson.
No entanto, ele e Karp encontraram um algoritmo randomizado para um determinado problema difícil que mais tarde foram capazes de desrandomizar, descobrindo efetivamente um algoritmo determinístico para ele.
Na mesma época, outros pesquisadores mostraram como as suposições de dureza computacional em problemas de criptografia poderiam permitir a desrandomização em geral.
A eficácia irracional da aleatoriedade levou-o a pensar sobre a natureza da própria aleatoriedade.
Ele, como outros pesquisadores da época, questionou até que ponto isso era necessário para a resolução eficiente de problemas e em que condições poderia ser totalmente eliminado.
“Inicialmente, não estava claro se isso era apenas nossa própria estupidez, que não podemos eliminar a aleatoriedade”, disse ele.
“Mas a questão maior era se a aleatoriedade sempre pode ser eliminada de forma eficiente ou não.” Ele percebeu que a necessidade de aleatoriedade estava intimamente ligada à dificuldade computacional do problema.
Para um artigo de 1994, ele e o cientista da computação Noam Nisan esclareceram essa conexão.
Eles provaram que, se existir algum problema natural difícil, como a maioria dos cientistas da computação suspeita, então todo algoritmo aleatório eficiente pode ser substituído por um determinístico eficiente.
“Você sempre pode eliminar a aleatoriedade”, disse Wigderson.
É importante ressaltar que eles descobriram que algoritmos determinísticos podem usar sequências “pseudo-aleatórias” – sequências de dados que parecem aleatórias, mas não são.
Eles também mostraram como qualquer problema difícil pode ser usado para construir um gerador pseudoaleatório.
Alimentar os bits pseudoaleatórios (em vez dos aleatórios) em um algoritmo probabilístico resultará em um algoritmo determinístico eficiente para o mesmo problema.
Sudão disse que o artigo ajudou os cientistas da computação a reconhecer graus de aleatoriedade que poderiam ajudar a revelar as complexidades de problemas difíceis e como resolvê-los.
“Não se trata apenas de aleatoriedade, mas de percepções de aleatoriedade”, disse ele.
“Essa é a chave.” Sudão salienta que a aleatoriedade parece aparecer em todo o lado, mas é, na verdade, extremamente difícil de encontrar.
“As pessoas dizem que os dígitos de pi parecem aleatórios, ou que a sequência de números primos parece aleatória”, disse ele.
“Eles estão completamente determinados, mas parecem aleatórios para nós.” A percepção da aleatoriedade, disse ele, está no cerne da ciência da computação hoje.
“E isso é algo que Avi promoveu amplamente.” A aleatoriedade tornou-se um recurso poderoso na teoria da complexidade, mas é evasivo.
Os lançamentos de moedas e de dados, ressalta Wigderson, não são verdadeiramente aleatórios: se você tiver informações suficientes sobre o sistema físico, o resultado será totalmente previsível.
A aleatoriedade perfeita, disse ele, é ilusória e difícil de verificar.
Mas para Wigderson, os exemplos de computação estão por toda parte – não apenas em smartphones, laptops e algoritmos de criptografia, mas também em sistemas biológicos e físicos.
Nas últimas décadas, as descobertas da teoria da computação produziram insights sobre uma série de problemas inesperados, desde enxames de pássaros e resultados eleitorais até reações bioquímicas no corpo.
“Basicamente, qualquer processo natural é uma evolução que você pode ver como computação, então você pode estudá-la como tal.
Quase tudo computa.”
Publicado em 13/04/2024 16h05
Artigo original: