Prêmio Gödel

Prêmio Gödel
Imagem associada ao prêmio
Kurt Gödel em 1925
Organizador EATCS e SIGACT
Data de criação 1992

O Prêmio Gödel é uma distinção criada em 1992 pela European Association for Theoretical Computer Science (EATCS) e o Special Interest Group on Algorithms and Computation Theory (SIGACT) da Association for Computing Machinery (ACM) para homenagear o trabalho notável de ' computador teórico ciência . É nomeado em homenagem ao lógico Kurt Gödel .

Descrição

O Prêmio Gödel é concedido anualmente desde 1993 e inclui um prêmio de US $ 5.000  . O preço distingue um item, em vez de um indivíduo. Para ser elegível, o artigo do destinatário deve ter sido publicado em um periódico com revisão por pares nos 14 anos anteriores. O Prêmio Gödel é considerado um dos dois maiores prêmios internacionais de ciência da computação, junto com o Prêmio Turing .

O prêmio é uma homenagem a Kurt Gödel, por seu trabalho em lógica matemática e sua intuição do problema P = NP .

Laureados

Lista de laureados
Ano Nome (s) Contribuição (ões)
1993 László Babai ( Hungria ) e Shlomo Moran ( Israel ), Shafi Goldwasser ( Israel / Estados Unidos ), Silvio Micali ( Itália / Estados Unidos ) e Charles Rackoff ( Estados Unidos ) Desenvolvimento do conceito de sistema de prova interativo
1994 Johan Håstad ( Suécia ) Terminais em problemas de circuito booleano e, em particular, na função de paridade
1995 Neil Immerman ( Estados Unidos ) e Róbert Szelepcsényi ( Eslováquia ) Seu teorema que liga as classes NSPACE e co-NSPACE
1996 Mark Jerrum ( Reino Unido ) e Alistair Sinclair ( Reino Unido ) Seu trabalho em cadeias de Markov e a aproximação permanente
1997 Joseph Halpern ( Estados Unidos ) e Yoram Moses ( Israel ) O desenvolvimento da noção de informação no contexto de sistemas distribuídos
1998 Seinosuke Toda ( Japão ) Seu teorema relacionando as classes de complexidade PP e PH
1999 Peter Shor ( Estados Unidos ) O algoritmo Shor , que permite fatorar números em tempo polinomial em um computador quântico
2000 Moshe Vardi ( Israel ) e Pierre Wolper ( Bélgica ) Seu trabalho em lógica temporal no contexto de autômatos finitos
2001 Sanjeev Arora ( Estados Unidos ), Uriel Feige ( Israel ), Shafi Goldwasser ( Israel / Estados Unidos ), Carsten Lund ( Dinamarca ), László Lovász ( Hungria / Estados Unidos ), Rajeev Motwani ( Índia ), Shmuel Safra ( Israel ), Madhu Sudão ( Estados Unidos ) e Mario Szegedy ( Hungria / Estados Unidos ) Seu teorema PCP
2002 Géraud Sénizergues ( França ) Demonstraram a decidibilidade da igualdade das duas línguas reconhecido por determinista autômatos empilhado
2003 Yoav Freund ( Israel ) e Robert Schapire ( Estados Unidos ) O algoritmo AdaBoost em aprendizado de máquina
2004 Maurice Herlihy ( Estados Unidos ), Michael Saks ( Estados Unidos ), Nir Shavit ( Israel ), Fotios Zaharoglou ( Grécia ) A aplicação de conceitos de topologia para computação distribuída
2005 Noga Alon ( Israel ), Yossi Matias ( Israel ) e Mario Szegedy ( Hungria ) Suas contribuições para algoritmos de mineração de fluxo de dados
2006 Manindra Agrawal ( Índia ), Neeraj Kayal ( Índia ) e Nitin Saxena ( Índia ) O teste de primalidade AKS
2007 Alexandre Razborov ( Rússia ) e Steven Rudich ( Estados Unidos ) Seu artigo seminal sobre prova natural
2008 Shang-Hua Teng ( China ) e Daniel Spielman ( Estados Unidos ) O algoritmo de análise suave ( análise suavizada )
2009 Omer Reingold ( Israel ), Salil Vadhan ( Estados Unidos ) e Avi Wigderson ( Israel ) O produto em zigue-zague dos gráficos
2010 Sanjeev Arora ( Estados Unidos ) e Joseph SB Mitchell ( Estados Unidos ) O esquema de aproximação polinomial do problema do caixeiro viajante no caso euclidiano
2011 Johan Håstad ( Suécia ) Resultados de dificuldade de aproximação , ligados ao teorema PCP
2012 Elias Koutsoupias ( Grécia ), Christos Papadimitriou ( Grécia ), Noam Nisan ( Israel ), Amir Ronen ( Israel ), Tim Roughgarden ( Estados Unidos ) e Éva Tardos ( Hungria ) A criação da teoria dos jogos algorítmicos
2013 Dan Boneh ( Israel ), Matthew K. Franklin ( Estados Unidos ) e Antoine Joux ( França ) A introdução da criptografia baseada em acoplamento
2014 Ronald Fagin ( Estados Unidos ), Amnon Lotem ( Israel ) e Moni Naor ( Israel ) Algoritmos de agregação ideal
2015 Shang-Hua Teng ( China ) e Daniel Spielman ( Estados Unidos ) Seu trabalho em álgebra linear digital e a aplicação de algoritmos de gráfico e teoria de gráfico espectral
2016 Stephen D. Brookes ( Reino Unido ) e Peter O'Hearn ( Canadá ) A invenção da lógica de separação simultânea
2017 Cynthia Dwork ( Estados Unidos ), Frank McSherry ( Estados Unidos ), Kobbi Nissim ( Israel ) e Adam D. Smith ( Estados Unidos ) A invenção da confidencialidade diferencial
2018 Oded Regev ( Israel ) A introdução do problema de aprendizagem com erros , o estudo da sua complexidade em média por redução aos problemas das redes euclidianas e o seu impacto na criptografia pós-quântica
2019 Irit Dinur ( Israel ) Para uma prova fundamentalmente diferente do teorema PCP , mais simples, mais direta e mais eficiente.
2020 Robin A. Moser e Gábor Tardos ( Hungria ) Para uma versão algorítmica do lema local de Lovász .
2021 Andrei Bulatov, Jin-Yi Cai, Xi Chen, Martin Dyer ( Reino Unido ) e David Richerby Classificação da complexidade de contagem  (in) os problemas de satisfação de restrição .

Artigos Distintos

  1. László Babai e Shlomo Moran , “  Arthur-Merlin games: a randomized proof system, and a hierarchy of complex class  ”, Journal of Computer and System Sciences , vol.  36, n o  21988, p.  254-276 ( DOI  10.1016 / 0022-0000 (88) 90028-1 , leia online )
  2. S. Goldwasser , S. Micali e C. Rackoff , “  A complexidade do conhecimento dos sistemas de prova interativa  ”, SIAM Journal on Computing , vol.  18, n o  1,1989, p.  186–208 ( DOI  10.1137 / 0218012 , leia online )
  3. Johan Håstad , “Limites Inferiores Quase Ótimos para Circuitos de Profundidade Pequena” , em Silvio Micali (editor), Randomness and Computation , JAI Press, col.  "Advances in Research Computação" ( n O  5),1989( ISBN  0-89232-896-7 , leia online [ arquivo de22 de fevereiro de 2012] ), “Limites inferiores quase ideais para circuitos de pequena profundidade”,p.  6-20
  4. Neil Immerman , “  Nondeterministic space is closed under complementation,  ” SIAM Journal on Computing , vol.  17, n o  5,1988, p.  935-938 ( ISSN  1095-7111 , DOI  10.1137 / 0217058 , leia online )
  5. R. Szelepcsényi , “  O método de enumeração forçada para autômatos não determinísticos  ”, Acta Informatica , vol.  26, n o  3,1988, p.  279-284 ( DOI  10.1007 / BF00299636 )
  6. Mark Jerrum e Alistair Sinclair , “  Approximating the permanent  ”, SIAM Journal on Computing , vol.  18, n o  6,1989, p.  1149-1178 ( ISSN  1095-7111 , DOI  10.1137 / 0218077 )
  7. Alistair Sinclair e Mark Jerrum , “  Contagem aproximada, geração uniforme e cadeias de Markov de mistura rápida  ”, Informação e Computação , vol.  82, n o  1,1989, p.  93–133 ( DOI  10.1016 / 0890-5401 (89) 90067-9 )
  8. Joseph Halpern e Yoram Moses , “  Conhecimento e conhecimento comum em um ambiente distribuído,  ” Journal of the ACM , vol.  37, n o  3,1990, p.  549-587 ( DOI  10.1145 / 79147.79161 )
  9. Seinosuke Toda , “  PP é tão difícil quanto a hierarquia de tempo polinomial  ”, SIAM Journal on Computing , vol.  20, n o  5,1991, p.  865-877 ( DOI  10.1137 / 0220053 , leia online )
  10. Peter W. Shor , “  Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer  ”, SIAM Journal on Computing , vol.  26, n o  5,1997, p.  1484-1509 ( DOI  10.1137 / S0097539795293172 , leia online )
  11. Moshe Y. Vardi e Pierre Wolper , “  Reasoning about infinite computations  ”, Information and Computation , vol.  115, n o  1,1994, p.  1-37 ( DOI  10.1006 / inco.1994.1092 , leia online [ arquivo de25 de agosto de 2011] )
  12. Uriel Feige , Shafi Goldwasser , Laszlo Lovász , Shmuel Safra e Mario Szegedy , “  Provas interativas e a dureza de cliques aproximados  ”, Journal of the ACM , vol.  43, n o  21996, p.  268-292 ( DOI  10.1145 / 226643.226652 , leia online )
  13. Sanjeev Arora e Shmuel Safra , “  Verificação probabilística de provas: uma nova caracterização de NP  ”, Journal of the ACM , vol.  45, n o  1,1998, p.  70-122 ( DOI  10.1145 / 273865.273901 , leia online [ arquivo de10 de junho de 2011] )
  14. Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan e Mario Szegedy , “  A verificação da prova e a dureza dos problemas de aproximação  ”, Journal of the ACM , vol.  45, n o  3,1998, p.  501-555 ( DOI  10.1145 / 278298.278306 , leia online [ arquivo de10 de junho de 2011] )
  15. Géraud Sénizergues , “  L (A) = L (B)? a decidibilidade resulta de sistemas formais completos  ”, Theor. Comput. Sci. , vol.  251 n o  12001, p.  1-166 ( DOI  10.1016 / S0304-3975 (00) 00285-1 )
  16. Y. Freund e RE Schapire , “  Uma generalização da teoria da decisão da aprendizagem on-line e uma aplicação para impulsionar  ”, Journal of Computer and System Sciences , vol.  55, n o  1,1997, p.  119–139 ( DOI  10.1006 / jcss.1997.1504 , leia online )
  17. Maurice Herlihy e Nir Shavit, “  A estrutura topológica da computação assíncrona  ”, Journal of the ACM , vol.  46, n o  6,1999, p.  858-923 ( DOI  10.1145 / 331524.331529 , leia online )
  18. Michael Saks e Fotios Zaharoglou , “O  acordo de k - set sem espera é impossível: A topologia do conhecimento público  ”, SIAM Journal on Computing , vol.  29, n o  5,2000, p.  1449–1483 ( DOI  10.1137 / S0097539796307698 )
  19. Noga Alon , Yossi Matias e Mario Szegedy , “  A complexidade espacial da aproximação dos momentos de frequência  ”, Journal of Computer and System Sciences , vol.  58, n o  1,1999, p.  137-147 ( DOI  10.1006 / jcss.1997.1545 , leia online )
  20. Manindra Agrawal, Neeraj Kayal e Nitin Saxena, “  PRIMES está em P  ”, Annals of Mathematics , vol.  160, n o  22004, p.  781-793 ( DOI  10.4007 / annals.2004.160.781 , leia online [ arquivo de7 de junho de 2011] )
  21. Alexander A. Razborov e Steven Rudich , "  Natural proofs  ", Journal of Computer and System Sciences , vol.  55, n o  1,1997, p.  24-35 ( DOI  10.1006 / jcss.1997.1494 )
  22. Daniel A. Spielman e Shang-Hua Teng , “  Smoothed analysis of algorítmos: Por que o algoritmo simplex geralmente leva tempo polinomial  ”, Journal of the ACM , vol.  51, n o  3,2004, p.  385-463 ( leia online [ arquivo de6 de dezembro de 2009] )
  23. Omer Reingold , Salil Vadhan e Avi Wigderson , “  Ondas de entropia, o produto gráfico em zigue-zague e novos expansores de grau constante  ”, Annals of Mathematics , vol.  155, n o  1,2002, p.  157-187 ( DOI  10.2307 / 3062153 , JSTOR  3062153 , Math Reviews  1888797 , leia online [ arquivo de7 de dezembro de 2009] )
  24. Omer Reingold , “  Conectividade não direcionada no espaço de log  ” , Journal of the ACM , vol.  55, n o  4,2008, p.  1-24 ( ler online )
  25. Sanjeev Arora , “  Esquemas de aproximação de tempo polinomial para caixeiro viajante euclidiano e outros problemas geométricos  ”, Journal of the ACM , vol.  45, n o  5,1998, p.  753-782 ( DOI  10.1145 / 290179.290180 )
  26. Joseph SB Mitchell , "  Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems  ", SIAM Journal on Computing , vol.  28, n o  4,1999, p.  1298-1309 ( ISSN  1095-7111 , DOI  10.1137 / S0097539796309764 )
  27. Johan Håstad , “  Alguns resultados ótimos de improximabilidade  ”, Journal of the ACM , vol.  48,2001, p.  798-859 ( DOI  10.1145 / 502090.502098 , leia online )
  28. Elias Koutsoupias e Christos Papadimitriou , “  Worst-case equilibria  ”, Computer Science Review , vol.  3, n o  22009, p.  65–69 ( DOI  10.1016 / j.cosrev.2009.04.003 )
  29. Tim Roughgarden e Éva Tardos , “  Quão ruim é o roteamento egoísta?  ”, Journal of the ACM , vol.  49, n o  22002, p.  236-259 ( DOI  10.1145 / 506147.506153 )
  30. Noam Nisan e Amir Ronen , “  Algorithmic Mechanism Design  ”, Games and Economic Behavior , vol.  35, n osso  1-2,2001, p.  166–196 ( DOI  10.1006 / game.1999.0790 )
  31. Dan Boneh e Matthew Franklin , “  Identity-based encryption from the Weil pairing,  ” SIAM Journal on Computing , vol.  32, n o  3,2003, p.  586–615 ( DOI  10.1137 / S0097539701398521 , Math Reviews  2001745 )
  32. Antoine Joux , "  A one round protocol for tripartite Diffie-Hellman  ", Journal of Cryptology , vol.  17, n o  4,2004, p.  263-276 ( DOI  10.1007 / s00145-004-0312-y , Math Reviews  2090557 )
  33. Ronald Fagin , Amnon Lotem e Moni Naor , “  Optimal aggregation algoritms for middleware  ”, Journal of Computer and System Sciences , vol.  66, n o  4,2003, p.  614-656 ( DOI  10.1016 / S0022-0000 (03) 00026-6 )
  34. Daniel A. Spielman e Shang-Hua Teng , “  Spectral Sparsification of Graphs  ”, SIAM Journal on Computing , vol.  40, n o  4,2011, p.  981-1025 ( ISSN  0097-5397 , DOI  10.1137 / 08074489X ).
  35. Daniel A. Spielman e Shang-Hua Teng , “  A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning  ”, SIAM Journal on Computing , vol.  42, n o  1,2013, p.  1-26 ( ISSN  0097-5397 , DOI  10.1137 / 080744888 ).
  36. Daniel A. Spielman e Shang-Hua Teng , "  Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominante Linear Systems  ", SIAM Journal on Matrix Analysis and Applications , vol.  35, n o  3,2014, p.  835-885 ( ISSN  0895-4798 , DOI  10.1137 / 090771430 ).
  37. Peter W. O'Hearn, "  Resources, Concurrency, and Local Reasoning,  " Theoretical Computer Science , vol.  375, n osso  1-3, 2007, p.  271-307.
  38. Stephen Brookes, “  A Semantics for Concurrent Separation Logic,  ” Theoretical Computer Science , vol.  375, n osso  1-3, 2007, p.  227-270.
  39. Cynthia Dwork, Frank McSherry, Kobbi Nissim e Adam Smith, “  Calibrating Noise to Sensitivity  ”, Jornal de Análise de Dados Privados de Privacidade e Confidencialidade , vol.  7, n o  3,2016.
  40. (in) Oded Regev , "  We lattices, learning with errors, random linear codes and cryptography  " , Journal of the ACM , vol.  56, n o  6, 2009, p.  34: 1-34: 40 ( DOI  10.1145 / 1568318.1568324 ).
  41. (em) Irit Dinur , "  The PCP teorema por amplification gap  ' , Journal of the ACM , vol.  54, n o  3, 2007, p.  12
  42. (em) Robin A. Moser e Gábor Tardos , "  uma prova construtiva do Lema local geral de Lovász  " , Journal of the ACM , vol.  57, n o  2 2010, p.  11: 1-11: 15
  43. Andrei A. Bulatov, “  A complexidade do problema de satisfação de restrição de contagem  ”, Journal of the ACM , Association for Computing Machinery (ACM), vol.  60, n o  5,2013, p.  1-41 ( ISSN  0004-5411 , DOI  10.1145 / 2528400 )
  44. Martin Dyer e David Richerby , “  An Effective Dicotomy for the Counting Constraint Satisfaction Problem  ”, Society for Industrial & Applied Mathematics (SIAM) , vol.  42, n o  3, 2013, p.  1245-1274 ( ISSN  0097-5397 , DOI  10.1137 / 100811258 )
  45. Jin-Yi Cai e Xi Chen, "  Complexity of Counting CSP with Complex Weights  " , Association for Computing Machinery (ACM) , vol.  64, n o  3, 22 de junho de 2017, p.  1-39 ( ISSN  0004-5411 , DOI  10.1145 / 2822891 )

Notas

Notas

  1. Primeiros parágrafos da página de preços
  2. Jacques Stern , "  Antoine Joux, Prix Gödel 2013  ", 1024 - Boletim da sociedade de TI da França , n o  1,Setembro de 2013, p.  107-110 ( ler online )
  3. No site EATCS: Prêmio é nomeado em homenagem a Kurt Gödel em reconhecimento de suas principais contribuições para a lógica matemática e de seu interesse, descoberto em uma carta que escreveu a John von Neumann pouco antes da morte de Neumann, no que se tornou o famoso " P versus NP "questão.
  4. Anúncio oficial do Prêmio Gõdel 2014 .
  5. Artigo sobre o artigo e o prêmio: Thore Husfeldt, “  Personal reality (Gödel Prize 2014)  ” [ arquivo du4 de maio de 2015] ,2014(acessado em 30 de abril de 2015 ) .
  6. "  Prêmio Gödel 2015  " , no SIGACT
  7. "  Prêmio Gödel 2016  " , no EATCS
  8. "  Prêmio Gödel 2017  " , no EATCS .
  9. "  Citação do Prêmio Gödel 2021  "
(fr) Este artigo foi retirado parcial ou totalmente do artigo da Wikipedia em inglês intitulado "  Prêmio Gödel  " ( veja a lista de autores ) .

Veja também

Artigo relacionado

links externos