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

 (awards.acm.org)
1 pontos por GN⁺ 2024-04-12 | 1 comentários | Compartilhar no WhatsApp
  • A ACM selecionou Avi Wigderson como o vencedor do ACM A.M. Turing Award de 2023, reconhecendo sua contribuição para uma nova compreensão da teoria da computação e do papel da aleatoriedade na computação
  • Wigderson é Herbert H. Maass Professor no Institute for Advanced Study e foi uma figura de liderança em teoria da complexidade computacional, além de algoritmos, criptografia, computação paralela e distribuída, combinatória e teoria dos grafos
  • Sua principal realização é a pesquisa em hardness for randomness, mostrando que, sob hipóteses computacionais amplamente aceitas, algoritmos probabilísticos de tempo polinomial podem ser simulados de forma determinística
  • Os trabalhos relacionados apresentaram geradores pseudoaleatórios, simulações em tempo subexponencial de BPP e compromissos hardness-vs-randomness, influenciando várias áreas da ciência da computação teórica
  • O Turing Award concede um prêmio de US$ 1 milhão com apoio do Google, e Wigderson também é reconhecido não apenas por suas conquistas técnicas, mas como mentor de jovens pesquisadores

Contexto do Prêmio Turing da ACM

  • A ACM selecionou Avi Wigderson como o vencedor do ACM A.M. Turing Award de 2023
  • O prêmio foi concedido por suas contribuições fundamentais à teoria da computação, por reformular a compreensão do papel da aleatoriedade na computação e por sua liderança intelectual demonstrada ao longo de décadas na ciência da computação teórica
  • Wigderson é Herbert H. Maass Professor no Departamento de Matemática do Institute for Advanced Study, em Princeton, Nova Jersey

  • Principais áreas de atuação

    • teoria da complexidade computacional
    • algoritmos e otimização
    • aleatoriedade e criptografia
    • computação paralela e distribuída
    • combinatória e teoria dos grafos
    • conexões entre ciência da computação teórica e matemática/ciência
    • O ACM A.M. Turing Award é chamado de “Nobel da computação” e oferece um prêmio de US$ 1 milhão com apoio financeiro da Google, Inc.
    • O prêmio leva o nome do matemático britânico Alan M. Turing, que estabeleceu as bases matemáticas da computação

Perguntas tratadas pela ciência da computação teórica

  • A ciência da computação teórica trata dos fundamentos matemáticos da computação e lida com perguntas como “este problema pode ser resolvido computacionalmente?” e “se pode, quanto tempo e recursos são necessários?”
  • A área também explora princípios para o projeto de algoritmos eficientes
  • Algoritmos são a base que torna possível a tecnologia computacional usada no dia a dia
  • A ciência da computação teórica também enfrenta desafios intelectuais que nem sempre melhoram aplicações práticas de imediato, mas avanços de pesquisa podem levar ao progresso em várias áreas
    • criptografia
    • biologia computacional
    • projeto de redes
    • aprendizado de máquina
    • computação quântica

Por que a aleatoriedade é importante na computação

  • Computadores são, em essência, sistemas determinísticos, e para uma dada entrada o conjunto de instruções de um algoritmo determina de forma única o cálculo e a saída
  • Aleatoriedade significa um estado em que não há padrão claro nem previsibilidade em eventos ou resultados
  • No mundo real, há muitos eventos que parecem aleatórios, como sistemas climáticos, fenômenos biológicos e fenômenos quânticos
  • Cientistas da computação vêm expandindo algoritmos para que façam escolhas aleatórias durante o processo computacional a fim de aumentar a eficiência
  • Muitos problemas para os quais não se conheciam algoritmos determinísticos eficientes também podem ser resolvidos eficientemente por algoritmos probabilísticos com pequena probabilidade de erro
    • Essa probabilidade de erro pode ser reduzida de forma eficiente
  • As perguntas centrais são se a aleatoriedade é essencial, se pode ser eliminada e qual qualidade de aleatoriedade é necessária para o sucesso de algoritmos probabilísticos
  • Entender melhor como funcionam a aleatoriedade e a pseudoaleatoriedade na computação pode levar ao desenvolvimento de algoritmos melhores e a uma compreensão mais profunda da própria natureza da computação

Principais contribuições de pesquisa de Wigderson

  • Wigderson é uma figura que lidera a pesquisa em ciência da computação teórica há 40 anos e fez contribuições fundamentais para entender o papel da aleatoriedade e da pseudoaleatoriedade na computação
  • Cientistas da computação descobriram uma conexão importante entre aleatoriedade e dificuldade computacional, isto é, a identificação de problemas naturais para os quais não existem algoritmos eficientes
  • Wigderson e seus coautores publicaram trabalhos influentes sobre hardness for randomness
  • Esses trabalhos mostraram que, sob hipóteses computacionais padrão e amplamente aceitas, todos os algoritmos probabilísticos de tempo polinomial podem ser derandomizados de forma eficiente
  • Esse resultado sugere que a aleatoriedade pode não ser estritamente necessária para a computação eficiente
  • Essa linha de pesquisa mudou o papel da aleatoriedade na computação e a forma de pensar sobre ela

  • Três artigos representativos

Alcance do impacto e conquistas adicionais

  • Os três artigos de Wigderson influenciaram muitas áreas da ciência da computação teórica para além de aleatoriedade e derandomização
  • As ideias desses trabalhos foram aproveitadas posteriormente em artigos influentes de vários pesquisadores importantes
  • Em um artigo com Omer Reingold, Salil Vadhan e Michael Capalbo, ele apresentou a primeira construção combinatória eficiente de expander graph
    • expander graph é um grafo esparso com fortes propriedades de conectividade
    • tem aplicações importantes tanto na matemática quanto na ciência da computação teórica
  • Além da aleatoriedade, Wigderson também demonstrou liderança intelectual nas seguintes áreas
    • multi-prover interactive proofs
    • criptografia
    • complexidade de circuitos

Mentoria e avaliação

  • Wigderson é reconhecido não apenas por contribuições técnicas revolucionárias, mas também como um respeitado mentor e colega que orientou muitos jovens pesquisadores
  • Seu vasto conhecimento, capacidade técnica, cordialidade, entusiasmo e generosidade são apontados como fatores que levaram excelentes jovens pesquisadores a seguir carreira em ciência da computação teórica
  • O presidente da ACM, Yannis Ioannidis, afirmou que Wigderson também recebeu o Prêmio Abel, considerado uma das mais importantes honrarias por realizações de uma vida inteira na matemática
  • Ioannidis avaliou que a matemática é a base da ciência da computação e que o trabalho de Wigderson conectou várias subáreas da matemática à ciência da computação teórica
  • Jeff Dean, Senior Vice President do Google, afirmou que a pesquisa de Wigderson sobre aleatoriedade e outros temas definiu a agenda da ciência da computação teórica nos últimos 30 anos
  • Dean também destacou que Wigderson foi um mentor que criou ideias e direções de pesquisa e motivou jovens pesquisadores a trabalhar nessas direções

O Turing Award e outros artigos importantes de Wigderson

Leituras relacionadas

1 comentários

 
GN⁺ 2024-04-12
Opiniões no Hacker News

  • Dois dos principais artigos de Wigderson mencionados no anúncio foram escritos em coautoria com Noam Nisan, um dos professores que criou o conhecido curso online From Nand to Tetris

    • O professor Nisan também é uma figura extraordinária. Depois de obter resultados de primeira linha em teoria da computação, ele também teve grande impacto em uma área bem diferente, a teoria algorítmica dos jogos
      É legal ver que uma pessoa consiga realizações tão diversas, e também impressiona um sistema que permite essa flexibilidade
    • Também há um livro. A 2ª edição saiu recentemente

  • Há também uma boa matéria da Quanta: https://www.quantamagazine.org/avi-wigderson-complexity-theo...
    Achei engraçada a variedade de poses que pediram para Wigderson fazer. Parece tudo muito constrangedor. Algo como: “Pronto, sente nesta cadeira e olhe pensativamente pela janela”

    • A parte em que “a eficácia irracional da aleatoriedade” levou Wigderson a pensar na própria natureza da aleatoriedade é interessante
      Entendo que classes de complexidade tratam do desempenho no pior caso, mas gostaria de ter uma noção geral de como se prova que, mesmo com bons geradores pseudoaleatórios e bons algoritmos randomizados, nenhuma combinação de RNG + seed + problem instance levará tempo exponencial
    • Pela correção, a matéria original dizia que Wigderson havia estudado na University of Haifa, mas na verdade ele se formou no Technion, em Haifa, Israel
      Fico curioso para saber como o repórter confundiu isso
    • A pose de “sentar na cadeira olhando pela janela” parece algo no estilo Martin Scorsese ou Sopranos. Uma cena de um gangster velho em uma casa de repouso

  • Há um texto em que Scott Aaronson conta como uma palestra de Avi Wigderson influenciou sua trajetória profissional: https://scottaaronson.blog/?p=2925

  • “Israeli Wins Turing Prize, Computing's Highest Honor, for Insights on Randomness” traz informações adicionais: [1] e cópia arquivada [2]
    [1] https://www.haaretz.com/israel-news/2024-04-10/ty-article/.p...
    [2] https://archive.is/e8uix

  • Fico imaginando por onde seria bom começar para acompanhar a parte da pesquisa de Wigderson sobre a troca entre dificuldade e aleatoriedade
    Não é comum eu nunca ter ouvido falar de um vencedor do Turing Award, mas essa pessoa estava completamente fora do meu radar

    • Dá para ver o livro dele: https://www.math.ias.edu/avi/book
    • Fico curioso sobre o que seriam “suposições computacionais padrão e amplamente aceitas”
      Imagino que talvez signifique que aproximação probabilística para problemas NP-completos também não está em tempo polinomial, ou então fico confuso se quer dizer que a versão sem aleatoriedade ainda é um algoritmo de aproximação

  • Acabei de pegar o livro de Wigderson e, até agora, estou gostando: https://press.princeton.edu/books/hardcover/9780691189130/ma...

    • Para pesquisa pessoal e fins educacionais, o rascunho final do livro pode ser visto aqui: https://www.math.ias.edu/avi/book
    • Dei uma olhada no livro e ele parece mais adequado a alunos de pós-graduação ou de graduação avançada
      Fico imaginando se alguém poderia recomendar um livro que trate de temas de computação de forma mais básica para quem está com a formação de graduação em ciência da computação/matemática meio enferrujada

  • Há esta frase em uma matéria relacionada: https://www.quantamagazine.org/avi-wigderson-complexity-theo...
    “Se uma afirmação é demonstrável, então ela também tem uma prova de conhecimento zero” — isso dá a sensação de explodir a cabeça
    E também é absurdamente surpreendente que “se você alimentar um algoritmo probabilístico com bits pseudoaleatórios em vez de bits aleatórios, isso vira um algoritmo determinístico eficiente para o mesmo problema”
    Como IA também é computação probabilística, se estou lendo corretamente, isso não significaria que dá para reduzir a complexidade dos modelos atuais em várias ordens de magnitude? Se for uma confusão de iniciante, espero que alguém me tire dela

    • Não sei exatamente o que isso quer dizer, mas pelo menos não é isso. IA já usa pseudoaleatoriedade e é determinística
      Há exceções, como alguns chips aceleradores de IA exóticos que usam computação analógica para aumentar a eficiência
    • Infelizmente, não. Primeiro, esse resultado se aplica a problemas de decisão, não a problemas de busca
      Segundo, o algoritmo determinístico resultante é muito menos eficiente que o algoritmo randomizado. Ele apenas pertence à mesma classe de complexidade sob hipóteses fracas

  • Gostei desta parte da matéria: “Aplicações não são a motivação, mas sabemos que até a pesquisa básica pode encontrar usos. Pense em Alan Turing. Ele escreveu um artigo matemático de lógica sobre o Entscheidungsproblem em uma revista pouco conhecida. Aplicações não eram a motivação”
    É parecido com a anedota do prato de Feynman. Começou com uma reação despretensiosa a algo que ele viu no refeitório da universidade e acabou levando ao Prêmio Nobel
    Ampliando a ideia, a academia moderna está caminhando justamente no sentido de sufocar esse tipo de investigação movida pela curiosidade

  • Segundo a ACM, Avi Wigderson foi escolhido como vencedor do ACM A.M. Turing Award de 2023 por suas contribuições fundamentais à teoria da computação, incluindo a reformulação da compreensão do papel da aleatoriedade na computação, e por décadas de liderança intelectual na ciência da computação teórica
    Wigderson é Herbert H. Maass Professor na Escola de Matemática do Institute for Advanced Study, em Princeton, Nova Jersey, e tem sido uma figura central em teoria da complexidade computacional, algoritmos e otimização, aleatoriedade e criptografia, computação paralela e distribuída, combinatória, teoria dos grafos e nas conexões entre ciência da computação teórica e matemática/ciência
    Em 2021, ele também recebeu o Prêmio Abel, formando uma combinação bastante rara de receber as maiores honrarias em matemática teórica/abstrata e ciência da computação

    • A sobreposição entre ciência da computação teórica e matemática é muito maior do que a maioria imagina
      Como exemplo simples, olhando a lista de disciplinas de ciência da computação teórica do MIT https://catalog.mit.edu/subjects/6/, dá para ver quantas disciplinas são oferecidas em conjunto com o curso 18, que é matemática
    • Estritamente falando, a maior honraria da matemática é a Medalha Fields
      Claro que eu não estou em posição de julgar

  • Gostaria de recomendações de materiais para estudar probabilidade/aleatoriedade e computação, de conteúdos amigáveis para iniciantes até avançados
    No Google aparece “Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis”, de Eli Upfal e Michael Mitzenmacher, mas não consigo encontrar bons livros, textos ou vídeos de nível básico/introdutório