Gödel-prisen

Gödel-prisen
Kurt Gödel i 1925
Arrangør	EATCS og SIGACT
Opprettelsesdato	1992

Den Gödel Prisen er en utmerkelse opprettet i 1992 av European Association for teoretisk informatikk (EATCS) og Special Interest Group on Algoritmer og Computation Theory (SIGACT) av Association for Computing Machinery (ACM) for å hedre fremragende arbeid av " teoretisk vitenskap . Den er oppkalt til ære for logikeren Kurt Gödel .

Beskrivelse

Gödel-prisen har blitt tildelt årlig siden 1993 og inkluderer en pris på USD 5000  . Pris skiller et element fremfor et individ. For å være kvalifisert må mottakerens artikkel ha blitt publisert i et fagfellevurdert tidsskrift i løpet av de siste 14 årene. Gödelprisen regnes som en av de to største internasjonale datavitenskapsprisene, sammen med Turingprisen .

Prisen er oppkalt til ære for Kurt Gödel, for hans arbeid innen matematisk logikk, og hans intuisjon av P = NP-problemet .

Prisvinnere

Distinguished Articles

1. László Babai og Shlomo Moran , “  Arthur-Merlin-spill: et randomisert bevis-system, og et hierarki av kompleksitetsklasse  ”, Journal of Computer and System Sciences , vol.  36, n o  to1988, s.  254–276 ( DOI  10.1016 / 0022-0000 (88) 90028-1 , les online )
2. S. Goldwasser , S. Micali og C. Rackoff , “  The knowledge complexity of interactive proof systems  ”, SIAM Journal on Computing , vol.  18, n o  1,1989, s.  186–208 ( DOI  10.1137 / 0218012 , les online )
3. Johan Håstad , “Nesten optimale nedre grenser for små dybdekretser ” , i Silvio Micali (redaktør), Randomness and Computation , JAI Press, koll.  "Fremskritt innen databehandling" ( nr .  5),1989( ISBN  0-89232-896-7 , leses online [ arkiv av22. februar 2012] ), “Nesten optimale nedre grenser for små dybdekretser”,s.  6–20
4. Neil Immerman , “Ikke-  deterministisk rom er lukket under komplementering,  ” SIAM Journal on Computing , vol.  17, n o  5,1988, s.  935–938 ( ISSN  1095-7111 , DOI  10.1137 / 0217058 , les online )
5. R. Szelepcsényi , “  Metoden for tvangsoppregning for ikke-deterministisk automata  ”, Acta Informatica , vol.  26, n o  3,1988, s.  279–284 ( DOI  10.1007 / BF00299636 )
6. Mark Jerrum og Alistair Sinclair , “  Approximating the permanent  ”, SIAM Journal on Computing , vol.  18, n o  6,1989, s.  1149–1178 ( ISSN  1095-7111 , DOI  10.1137 / 0218077 )
7. Alistair Sinclair og Mark Jerrum , "  Omtrentlig telling, ensartet generering og hurtig blanding av Markov-kjeder  ", Information and Computation , vol.  82, n o  1,1989, s.  93–133 ( DOI  10.1016 / 0890-5401 (89) 90067-9 )
8. Joseph Halpern og Yoram Moses , “  Kunnskap og felles kunnskap i et distribuert miljø,  ” Journal of the ACM , vol.  37, n o  3,1990, s.  549–587 ( DOI  10.1145 / 79147.79161 )
9. Seinosuke Toda , "  PP er like vanskelig som hierarkiet med polynom-tid  ", SIAM Journal on Computing , vol.  20, n o  5,1991, s.  865–877 ( DOI  10.1137 / 0220053 , les 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, s.  1484–1509 ( DOI  10.1137 / S0097539795293172 , les online )
11. Moshe Y. Vardi og Pierre Wolper , “  Reasoning about infinite computations  ”, Information and Computation , vol.  115, n o  1,1994, s.  1–37 ( DOI  10.1006 / inco.1994.1092 , les online [ arkiv av25. august 2011] )
12. Uriel Feige , Shafi Goldwasser , Laszlo Lovász , Shmuel Safra og Mario Szegedy , “  Interactive proofs and the hardness of approximating cliques  ”, Journal of the ACM , vol.  43, n o  to1996, s.  268–292 ( DOI  10.1145 / 226643.226652 , les online )
13. Sanjeev Arora og Shmuel Safra , “  Probabilistisk kontroll av bevis: en ny karakterisering av NP  ”, Journal of the ACM , vol.  45, n o  1,1998, s.  70–122 ( DOI  10.1145 / 273865.273901 , les online [ arkiv av10. juni 2011] )
14. Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan og Mario Szegedy , “  Proof verification and the hardness of approximation problems  ”, Journal of the ACM , vol.  45, n o  3,1998, s.  501–555 ( DOI  10.1145 / 278298.278306 , les online [ arkiv av10. juni 2011] )
15. Géraud Sénizergues , “  L (A) = L (B)? avgjørende resultater fra komplette formelle systemer  ”, Theor. Beregn. Sci. , vol.  251 n o  12001, s.  1–166 ( DOI  10.1016 / S0304-3975 (00) 00285-1 )
16. Y. Freund og RE Schapire , “  En beslutningsteoretisk generalisering av online læring og en applikasjon til boosting  ”, Journal of Computer and System Sciences , vol.  55, n o  1,1997, s.  119–139 ( DOI  10.1006 / jcss.1997.1504 , les online )
17. Maurice Herlihy og Nir Shavit, “  Den topologiske strukturen for asynkron beregning  ”, Journal of the ACM , vol.  46, n o  6,1999, s.  858–923 ( DOI  10.1145 / 331524.331529 , les online )
18. Michael Saks og Fotios Zaharoglou , “  Wait-free k -set agreement is impossible: The topology of public knowledge  ”, SIAM Journal on Computing , vol.  29, n o  5,2000, s.  1449–1483 ( DOI  10.1137 / S0097539796307698 )
19. Noga Alon , Yossi Matias og Mario Szegedy , “  The space complexity of approximating the frequency moments  ”, Journal of Computer and System Sciences , vol.  58, n o  1,1999, s.  137–147 ( DOI  10.1006 / jcss.1997.1545 , les online )
20. Manindra Agrawal, Neeraj Kayal og Nitin Saxena, “  PRIMES er i P  ”, Annals of Mathematics , vol.  160, n o  to2004, s.  781–793 ( DOI  10.4007 / annals.2004.160.781 , les online [ arkiv av7. juni 2011] )
21. Alexander A. Razborov og Steven Rudich , "  Natural proofs  ", Journal of Computer and System Sciences , vol.  55, n o  1,1997, s.  24–35 ( DOI  10.1006 / jcss.1997.1494 )
22. Daniel A. Spielman og Shang-Hua Teng , “  Utjevnet analyse av algoritmer: Hvorfor simpleksalgoritmen vanligvis tar polynomial tid  ”, Journal of the ACM , vol.  51, n o  3,2004, s.  385–463 ( les online [ arkiv av6. desember 2009] )
23. Omer Reingold , Salil Vadhan og Avi Wigderson , “ Entropibølger ,  sikksakkproduktet og nye utvidere med konstant grad  ”, Annals of Mathematics , vol.  155, n o  1,2002, s.  157–187 ( DOI  10.2307 / 3062153 , JSTOR  3062153 , Math Reviews  1888797 , les online [ arkiv av7. desember 2009] )
24. Omer Reingold , "  Udirigert tilkobling i log-space,  " Journal of the ACM , vol.  55, n o  4,2008, s.  1–24 ( les online )
25. Sanjeev Arora , “  Polynomial time approximation schemes for Euklidean travelling salesman and other geometric problems  ”, Journal of the ACM , vol.  45, n o  5,1998, s.  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, nr .  4,1999, s.  1298–1309 ( ISSN  1095-7111 , DOI  10.1137 / S0097539796309764 )
27. Johan Håstad , “  Some optimal inapproximability results  ”, Journal of the ACM , vol.  48,2001, s.  798–859 ( DOI  10.1145 / 502090.502098 , les online )
28. Elias Koutsoupias og Christos Papadimitriou , “  Worst-case equilibria  ”, Computer Science Review , vol.  3, n o  to2009, s.  65–69 ( DOI  10.1016 / j.cosrev.2009.04.003 )
29. Tim Roughgarden og Éva Tardos , “  Hvor ille er egoistisk ruting?  ”, Journal of the ACM , vol.  49, n o  to2002, s.  236–259 ( DOI  10.1145 / 506147.506153 )
30. Noam Nisan og Amir Ronen , “  Algorithmic Mechanism Design  ”, Games and Economic Behavior , vol.  35, n bein  1-2,2001, s.  166–196 ( DOI  10.1006 / game.1999.0790 )
31. Dan Boneh og Matthew Franklin , “  Identitetsbasert kryptering fra Weil-parring,  ” SIAM Journal on Computing , vol.  32, n o  3,2003, s.  586–615 ( DOI  10.1137 / S0097539701398521 , matematiske anmeldelser  2001745 )
32. Antoine Joux , “  A one round protocol for tripartite Diffie-Hellman  ”, Journal of Cryptology , vol.  17, n o  4,2004, s.  263–276 ( DOI  10.1007 / s00145-004-0312-y , matematikkanmeldelser  2090557 )
33. Ronald Fagin , Amnon Lotem og Moni Naor , “  Optimale aggregeringsalgoritmer for mellomvare  ”, Journal of Computer and System Sciences , vol.  66, n o  4,2003, s.  614-656 ( DOI  10.1016 / S0022-0000 (03) 00026-6 )
34. Daniel A. Spielman og Shang-Hua Teng , “  Spectral Sparsification of Graphs  ”, SIAM Journal on Computing , vol.  40, n o  4,2011, s.  981-1025 ( ISSN  0097-5397 , DOI  10.1137 / 08074489X ).
35. Daniel A. Spielman og Shang-Hua Teng , “  En lokal klyngealgoritme for massive grafer og dens anvendelse på nesten lineær tidsgrafpartisjonering  ”, SIAM Journal on Computing , vol.  42, n o  1,2013, s.  1-26 ( ISSN  0097-5397 , DOI  10.1137 / 080744888 ).
36. Daniel A. Spielman og Shang-Hua Teng , "  Nesten lineære tidsalgoritmer for forbehandling og løsning av symmetriske, diagonalt dominerende lineære systemer  ", SIAM Journal on Matrix Analysis and Applications , vol.  35, n o  3,2014, s.  835-885 ( ISSN  0895-4798 , DOI  10.1137 / 090771430 ).
37. Peter W. O'Hearn, “  Ressurser, samtidighet og lokal begrunnelse,  ” Teoretisk informatikk , vol.  375, n bein  1-3, 2007, s.  271-307.
38. Stephen Brookes, “  A Semantics for Concurrent Separation Logic,  ” Theoretical Computer Science , vol.  375, n bein  1-3, 2007, s.  227-270.
39. Cynthia Dwork, Frank McSherry, Kobbi Nissim og Adam Smith, “  Calibrating Noise to Sensitivity  ”, Private Data Analysis Journal of Privacy and Confidentiality , vol.  7, n o  3,2016.
40. (i) Oded Regev , "  Vi gitter, læring med feil, tilfeldige lineære koder og kryptografi  " , Journal of the ACM , vol.  56, n o  6, 2009, s.  34: 1-34: 40 ( DOI  10.1145 / 1568318.1568324 ).
41. (i) Irit Dinur , "  The PCP theorem by amplification gap  ' , Journal of the ACM , vol.  54, n o  3, 2007, s.  12
42. (i) Robin A. Moser og Gábor Tardos , "  konstruktivt Et bevis på det generelle Lovász Local Lemma  " , Journal of the ACM , vol.  57, n o  to 2010, s.  11: 1-11: 15
43. Andrei A. Bulatov, “  The complexity of the counting constraint tilfredshetsproblemet  ”, Journal of the ACM , Association for Computing Machinery (ACM), vol.  60, n o  5,2013, s.  1–41 ( ISSN  0004-5411 , DOI  10.1145 / 2528400 )
44. Martin Dyer og David Richerby , “  An Effektiv Dichotomy for the Counting Constraint Satisfaction Problem  ”, Society for Industrial & Applied Mathematics (SIAM) , vol.  42, n o  3, 2013, s.  1245–1274 ( ISSN  0097-5397 , DOI  10.1137 / 100811258 )
45. Jin-Yi Cai og Xi Chen, “  Complexity of Counting CSP with Complex Weights,  ” Association for Computing Machinery (ACM) , vol.  64, n o  3, 22. juni 2017, s.  1–39 ( ISSN  0004-5411 , DOI  10.1145 / 2822891 )

Merknader

Merknader

1. Første avsnitt på prissiden
2. Jacques Stern , "  Antoine Joux, Prix Gödel 2013  ", 1024 - Bulletin of the IT society of France , n o  1,September 2013, s.  107-110 ( les online )
3. På EATCS-nettstedet: Prisen blir kåret til ære for Kurt Gödel i anerkjennelse av hans store bidrag til matematisk logikk og for hans interesse, oppdaget i et brev han skrev til John von Neumann kort før Neumanns død, i det som har blitt den berømte " P versus NP "spørsmål.
4. Offisiell kunngjøring av 2014 Godel-prisen .
5. Artikkel om artikkelen og prisen: Thore Husfeldt, “  Personal reality (Gödel Prize 2014)  ” [ arkiv du4. mai 2015] ,2014(åpnet 30. april 2015 ) .
6. "  Gödel-prisen 2015  " , på SIGACT
7. "  2016 Gödel Prize  " , på EATCS
8. "  2017 Gödel Prize  " , på EATCS .
9. "  2021 Gödelpris sitering  "

Se også

Relatert artikkel

• Knuth-prisen

Eksterne linker

• Gödel-prisen på EATCS
• Gödel-pris på SIGACT