Gödel Ödülü

Gödel Ödülü
Ödülle ilgili resim
1925 yılında Kurt Gödel
Organizatör EATCS ve SIGACT
Oluşturulma tarihi 1992

Gödel Ödülü oluşturulan bir ayrımdır 1992 tarafından Teorik Bilgisayar Bilimi Avrupa Birliği (EATCS) ve Algoritmalar ve Hesaplama Teorisi üzerine Special Interest Group of (SIGACT) Association for Computing Machinery 'seçkin çalışmalarını onurlandırmak için (ACM) teorik bilgisayara bilim . Adını mantıkçı Kurt Gödel'e ithafen almıştır .

Açıklama

Gödel Ödülü 1993'ten beri her yıl verilmektedir ve 5.000 ABD Doları tutarındaki ödülü içermektedir  . Fiyat, bir bireyden ziyade bir öğeyi ayırt eder. Hak kazanmak için, alıcının makalesi önceki 14 yıl içinde hakemli bir dergide yayınlanmış olmalıdır. Gödel Ödülü, Turing Ödülü ile birlikte en büyük iki uluslararası bilgisayar bilimi ödülünden biri olarak kabul ediliyor .

Ödül, matematiksel mantıktaki çalışmaları ve P = NP problemindeki sezgileri nedeniyle Kurt Gödel'in onuruna verildi .

ödül sahipleri

ödüllü listesi
Yıl İsim(ler) Katkı(lar)
1993 László Babai ( Macaristan ) ve Shlomo Moran ( İsrail ), Shafi Goldwasser ( İsrail / Amerika Birleşik Devletleri ), Silvio Micali ( İtalya / Amerika Birleşik Devletleri ) ve Charles Rackoff ( Amerika Birleşik Devletleri ) Etkileşimli ispat sistemi kavramının geliştirilmesi
1994 Johan Håstad ( İsveç ) Boolean devre problemlerinde ve özellikle parite fonksiyonunda terminaller
1995 Neil Immerman ( Amerika Birleşik Devletleri ) ve Róbert Szelepcsényi ( Slovakya ) NSPACE ve ortak NSPACE sınıflarını birbirine bağlayan teoremleri
1996 Mark Jerrum ( İngiltere ) ve Alistair Sinclair ( İngiltere ) Üzerinde Çalışmaları Markov zincirlerinin ve kalıcı yaklaşım
1997 Joseph Halpern ( Amerika Birleşik Devletleri ) ve Yoram Moses ( İsrail ) Dağıtılmış sistemler bağlamında bilgi kavramının gelişimi
1998 Seinosuke Toda ( Japonya ) PP ve PH karmaşıklık sınıflarıyla ilgili teoremi
1999 Peter Shor ( Amerika Birleşik Devletleri ) Algoritması Şor bir üzerinde polinom zamanda faktör numaralara izin verir, kuantum bilgisayarın
2000 Moshe Vardi ( İsrail ) ve Pierre Wolper ( Belçika ) Sonlu otomatlar bağlamında zamansal mantık üzerine çalışmaları
2001 Sanjeev Arora ( Amerika Birleşik Devletleri ), Uriel Feige ( İsrail ), Shafi Goldwasser ( İsrail / Amerika Birleşik Devletleri ), Carsten Lund ( Danimarka ), László Lovász ( Macaristan / Amerika Birleşik Devletleri ), Rajeev Motwani ( Hindistan ), Shmuel Safra ( İsrail ), Madhu Sudan ( Amerika Birleşik Devletleri ) ve Mario Szegedy ( Macaristan / Amerika Birleşik Devletleri ) Onların PCP teoremi
2002 Géraud Sénizergues ( Fransa ) Deterministik yığılmış otomatlar tarafından tanınan iki dilin eşitliğinin karar verilebilirliğini gösterdiler
2003 Yoav Freund ( İsrail ) ve Robert Schapire ( Amerika Birleşik Devletleri ) AdaBoost algoritması içinde makine öğrenme
2004 Maurice Herlihy ( Amerika Birleşik Devletleri ), Michael Saks ( Amerika Birleşik Devletleri ), Nir Shavit ( İsrail ), Fotios Zaharoglou ( Yunanistan ) Uygulama topolojisi kavramları için dağıtılmış işlem
2005 Noga Alon ( İsrail ), Yossi Matias ( İsrail ) ve Mario Szegedy ( Macaristan ) Veri akışı madenciliği algoritmalarına katkıları
2006 Manindra Agrawal ( Hindistan ), Neeraj Kayal ( Hindistan ) ve Nitin Saxena ( Hindistan ) AKS asallık testi
2007 Alexandre Razborov ( Rusya ) ve Steven Rudich ( Amerika Birleşik Devletleri ) Doğal kanıtlarla ilgili ufuk açıcı makaleleri
2008 Shang-Hua Teng ( Çin ) ve Daniel Spielman ( Amerika Birleşik Devletleri ) Düz analiz algoritması ( düzleştirilmiş analizi )
2009 Omer Reingold ( İsrail ), Salil Vadhan ( Amerika Birleşik Devletleri ) ve Avi Wigderson ( İsrail ) Grafiklerin zikzaklı ürün
2010 Sanjeev Arora ( Amerika Birleşik Devletleri ) ve Joseph SB Mitchell ( ABD ) Polinom yaklaşımı şeması içinde gezgin satıcı problemi Öklid durumda
2011 Johan Håstad ( İsveç ) PCP teoremi ile bağlantılı yaklaşıklık zorluğunun sonuçları
2012 Elias Koutsoupias ( Yunanistan ), Christos Papadimitriou ( Yunanistan ), Noam Nisan ( İsrail ), Amir Ronen ( İsrail ), Tim Roughgarden ( ABD ) ve Éva Tardos ( Macaristan ) Algoritmik oyun teorisinin yaratılması
2013 Dan Boneh ( İsrail ), Matthew K. Franklin ( Amerika Birleşik Devletleri ) ve Antoine Joux ( Fransa ) Kuplaj tabanlı kriptografinin tanıtılması
2014 Ronald Fagin ( Amerika Birleşik Devletleri ), Amnon Lotem ( İsrail ) ve Moni Naor ( İsrail ) Optimum toplama algoritmaları
2015 Shang-Hua Teng ( Çin ) ve Daniel Spielman ( Amerika Birleşik Devletleri ) Sayısal lineer cebirdeki çalışmaları ve graf algoritmalarına ve spektral graf teorisine uygulamaları
2016 Stephen D. Brookes ( Birleşik Krallık ) ve Peter O'Hearn ( Kanada ) Eşzamanlı ayırma mantığının icadı
2017 Cynthia Dwork ( Amerika Birleşik Devletleri ), Frank McSherry ( ABD ), Kobbi Nissim ( İsrail ) ve Adam D. Smith ( Amerika Birleşik Devletleri ) Diferansiyel gizliliğin icadı
2018 Oded Regev ( İsrail ) Hatalarla öğrenme probleminin tanıtılması, Öklid ağlarının problemlerine indirgenerek ortalama olarak karmaşıklığının incelenmesi ve kuantum sonrası kriptografi üzerindeki etkisi
2019 Irit Dinur ( İsrail ) PCP teoreminden temelde farklı bir ispat için , daha basit, daha doğrudan ve daha verimli.
2020 Robin A. Moser ve Gábor Tardos ( Macaristan ) Lovász'ın yerel lemmasının algoritmik bir versiyonu için .
2021 Andrei Bulatov, Jin-Yi Cai, Xi Chen, Martin Dyer ( Birleşik Krallık ) ve David Richerby Sınıflandırılması sayma karmaşıklığı  (in) kısıt sağlama sorunların .

Seçkin Makaleler

  1. László Babai ve Shlomo Moran , “  Arthur-Merlin oyunları: randomize bir ispat sistemi ve karmaşıklık sınıfı hiyerarşisi  ”, Journal of Computer and System Sciences , cilt.  36, n o  21988, s.  254–276 ( DOI  10.1016 / 0022-0000 (88) 90028-1 , çevrimiçi okuyun )
  2. S. Goldwasser , S. Micali ve C. Rackoff , “  interaktif geçirmez sistemlerinin bilgi karmaşıklığı  ”, Bilişim'e yapılan SIAM Dergisi , cilt.  18, n o  1,1989, s.  186–208 ( DOI  10.1137 / 0218012 , çevrimiçi okuyun )
  3. Johan Håstad , “Küçük Derinlikli Devreler için Neredeyse Optimal Alt Sınırlar” , Silvio Micali (editör), Randomness and Computation , JAI Press, koll.  “Bilgisayar Araştırmalarındaki Gelişmeler” ( n o  5),1989( ISBN  0-89232-896-7 , çevrimiçi oku [ arşivi22 Şubat 2012] ), “Düşük Derinlikli Devreler için Neredeyse Optimal Alt Sınırlar”,s.  6-20
  4. Neil Immerman , “  Deterministik olmayan uzay tamamlama altında kapalıdır  ”, SIAM Journal on Computing , cilt.  17, n o  5,1988, s.  935–938 ( ISSN  1095-7111 , DOI  10.1137 / 0217058 , çevrimiçi okuyun )
  5. R. Szelepcsényi , “  Belirsiz olmayan otomatlar için zorunlu numaralandırma yöntemi  ”, Açta Informatica , cilt.  26, n o  3,1988, s.  279–284 ( DOI  10.1007 / BF00299636 )
  6. Mark Jerrum ve Alistair Sinclair , “  Approximating the kalıcı  ”, SIAM Journal on Computing , cilt.  18, n o  6,1989, s.  1149–1178 ( ISSN  1095-7111 , DOI  10.1137 / 0218077 )
  7. Alistair Sinclair ve Mark Jerrum , “  Yaklaşık sayma, tek biçimli üretim ve hızlı karıştırma Markov zincirleri  ”, Bilgi ve Hesaplama , cilt.  82, n veya  1,1989, s.  93–133 ( DOI  10.1016 / 0890-5401 (89) 90067-9 )
  8. Joseph Halpern ve Yoram Moses , “  Dağıtılmış bir ortamda bilgi ve ortak bilgi  ” Journal of the ACM , cilt.  37, n o  3,1990, s.  549–587 ( DOI  10.1145 / 79147.79161 )
  9. Seinosuke Toda , “  PP, polinom-zaman hiyerarşisi kadar zor  ”, SIAM Journal on Computing , cilt.  20, n o  5,1991, s.  865–877 ( DOI  10.1137 / 0220053 , çevrimiçi okuyun )
  10. Peter W. Shor , “  Bir Kuantum Bilgisayarında Asal Çarpanlara ayırma ve Ayrık Logaritmalar için Polinom Zamanlı Algoritmalar  ”, SIAM Journal on Computing , cilt.  26, n o  5,1997, s.  1484–1509 ( DOI  10.1137 / S0097539795293172 , çevrimiçi okuyun )
  11. Moshe Y. Vardi ve Pierre Wolper , “  Sonsuz hesaplamalar hakkında akıl yürütme  ”, Bilgi ve Hesaplama , cilt.  115, n o  1,1994, s.  1–37 ( DOI  10.1006 / inco.1994.1092 , çevrimiçi okuyun [ arşivi25 Ağu 2011] )
  12. Uriel Feige , Shafi Goldwasser , Laszlo Lovász , Shmuel Safra ve Mario Szegedy , “  Etkileşimli kanıtlar ve yaklaşık kliklerin sertliği  ”, Journal of the ACM , cilt.  43, n o  21996, s.  268–292 ( DOI  10.1145 / 226643.226652 , çevrimiçi okuyun )
  13. Sanjeev Arora ve Shmuel Safra , “  İspatların olasılıksal kontrolü: NP'nin yeni bir karakterizasyonu  ”, Journal of the ACM , cilt.  45, n o  1,1998, s.  70–122 ( DOI  10.1145 / 273865.273901 , çevrimiçi oku [ arşivi10 Haziran 2011] )
  14. Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan ve Mario Szegedy , “  Kanıt doğrulama ve yaklaşıklık problemlerinin sertliği  ”, Journal of the ACM , cilt.  45, n o  3,1998, s.  501–555 ( DOI  10.1145 / 278298.278306 , çevrimiçi oku [ arşivi10 Haziran 2011] )
  15. Géraud Sénizergues , “  L (A) = L (B)? karar verilebilirlik, tam biçimsel sistemlerden kaynaklanır  ”, Teori. Bilgisayar. bilim , cilt.  251 n o  12001, s.  1-166 ( DOI  10.1016 / S0304-3975 (00) 00.285-1 )
  16. Y. Freund ve RE Schapire , “  Çevrimiçi öğrenmenin karar-teorik bir genellemesi ve güçlendirmeye yönelik bir uygulama  ”, Journal of Computer and System Sciences , cilt.  55, n o  1,1997, s.  119–139 ( DOI  10.1006 / jcss.1997.1504 , çevrimiçi oku )
  17. Maurice Herlihy ve Nir Shavit, “  Asenkron hesaplamanın topolojik yapısı  ”, Journal of the ACM , cilt.  46, n o  6,1999, s.  858–923 ( DOI  10.1145 / 331524.331529 , çevrimiçi okuyun )
  18. Michael Saks ve Fotios Zaharoglou , “  Beklemesiz k - set anlaşması imkansız: Kamusal bilginin topolojisi  ”, SIAM Journal on Computing , cilt.  29, n o  5,2000, s.  1449–1483 ( DOI  10.1137 / S0097539796307698 )
  19. Noga Alon , Yossi Matias ve Mario Szegedy , “  Frekans momentlerine yaklaşmanın uzay karmaşıklığı  ”, Journal of Computer and System Sciences , cilt.  58, n o  1,1999, s.  137–147 ( DOI  10.1006 / jcss.1997.1545 , çevrimiçi okuyun )
  20. Manindra Agrawal, Neeraj Kayal ve Nitin Saxena, “  PRIMES is in P  ”, Annals of Mathematics , cilt.  160, n o  22004, s.  781–793 ( DOI  10.4007 / yıllıklar.2004.160.781 , çevrimiçi oku [ arşivi7 Haziran 2011] )
  21. Alexander A. Razborov ve Steven Rudich , "  Doğal kanıtlar  ", Journal of Computer and System Sciences , cilt.  55, n o  1,1997, s.  24-35 ( DOI  10.1006 / jcss.1997.1494 )
  22. Daniel A. Spielman ve Shang-Hua Teng , “  Algoritmaların düzleştirilmiş analizi: Neden tek yönlü algoritma genellikle polinom zaman alır  ”, Journal of the ACM , cilt.  51, n o  3,2004, s.  385–463 ( çevrimiçi oku [ arşivi6 Aralık 2009] )
  23. Omer Reingold , Salil Vadhan ve Avi Wigderson , “  Entropi dalgaları, zig-zag grafik ürünü ve yeni sabit derece genişleticiler  ”, Annals of Mathematics , cilt.  155, n o  1,2002, s.  157–187 ( DOI  10.2307 / 3062153 , JSTOR  3062153 , Matematik İncelemeleri  1888797 , çevrimiçi oku [ arşivi]7 Aralık 2009] )
  24. Omer Reingold , “  Günlük uzayında yönsüz bağlantı  ”, Journal of the ACM , cilt.  55, n o  4,2008, s.  1-24 ( çevrimiçi okuyun )
  25. Sanjeev Arora , “  Öklidci gezgin satıcı ve diğer geometrik problemler için polinom zaman yaklaşım şemaları  ”, Journal of the ACM , cilt.  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 Schema for Geometric TSP, k-MST ve İlgili Problemler  ”, SIAM Journal on Computing , cilt.  28, n o  4,1999, s.  1298-1309 ( ISSN  1095-7111 , DOI  10.1137 / S0097539796309764 )
  27. Johan Håstad , “  Bazı optimal yaklaştırmasızlık sonuçları  ”, Journal of the ACM , cilt.  48,2001, s.  798–859 ( DOI  10.1145 / 502090.502098 , çevrimiçi okuyun )
  28. Elias Koutsoupias ve Christos Papadimitriou , “  En kötü durum dengesi  ”, Computer Science Review , cilt.  3, n o  22009, s.  65–69 ( DOI  10.1016 / j.cosrev.2009.04.003 )
  29. Tim Roughgarden ve Éva Tardos , “  Bencil yönlendirme ne kadar kötü?  ”, ACM Dergisi , cilt.  49, n o  22002, s.  236–259 ( DOI  10.1145 / 506147.506153 )
  30. Noam Nisan ve Amir Ronen , “  Algorithmic Mechanism Design  ”, Games and Economic Behavior , cilt.  35, n kemik  1-2,2001, s.  166–196 ( DOI  10.1006 / oyun.1999.0790 )
  31. Dan Boneh ve Matthew Franklin , “  Weil eşleştirmesinden kimlik tabanlı şifreleme  ”, SIAM Journal on Computing , cilt.  32, n o  3,2003, s.  586–615 ( DOI  10.1137 / S0097539701398521 , Matematik İncelemeleri  2001745 )
  32. Antoine Joux , “  Üçlü Diffie-Hellman için tek turlu bir protokol  ”, Journal of Cryptology , cilt.  17, n o  4,2004, s.  263–276 ( DOI  10.1007 / s00145-004-0312-y , Matematik İncelemeleri  2090557 )
  33. Ronald Fagin , Amnon Lotem ve Moni Naor , “ Ara  katman yazılımı için Optimal toplama algoritmaları  ”, Journal of Computer and System Sciences , cilt.  66, n o  4,2003, s.  614-656 ( DOI  10.1016 / S0022-0000 (03) 00026-6 )
  34. Daniel A. Spielman ve Shang-Hua Teng , “  Grafiklerin Spektral Sparsification of Graphs  ”, SIAM Journal on Computing , cilt.  40, n o  4,2011, s.  981-1025 ( ISSN  0097-5397 , DOI  10.1137 / 08074489X ).
  35. Daniel A. Spielman ve Shang-Hua Teng , “  Massive Graphs için Yerel Kümeleme Algoritması ve Neredeyse Doğrusal Zaman Grafiği Bölümlemeye Uygulaması  ”, SIAM Journal on Computing , cilt.  42, n o  1,2013, s.  1-26 ( ISSN  0097-5397 , DOI  10.1137 / 080744888 ).
  36. Daniel A. Spielman ve Shang-Hua Teng , “  Nearly Linear Time Algorithms for Pre Conditioning and Solving Simetrik, Çapraz Baskın Lineer Sistemler  ”, SIAM Journal on Matrix Analysis and Applications , cilt.  35, n o  3,2014, s.  835-885 ( ISSN  0895-4798 , DOI  10.1137 / 090771430 ).
  37. Peter W. O'Hearn, “  Resources, Concurrency, and Local Reasoning,  ” Theoretical Computer Science , cilt.  375, n kemik  1-3, 2007, s.  271-307.
  38. Stephen Brookes, “  A Semantics for Concurrent Separation Logic  ”, Teorik Bilgisayar Bilimi , cilt.  375, n kemik  1-3, 2007, s.  227-270.
  39. Cynthia Dwork, Frank McSherry, Kobbi Nissim ve Adam Smith, “  Calibrating Noise to Sensitivity  ”, Private Data Analysis Journal of Privacy and Confidentiality , cilt.  7, n o  3,2016.
  40. (içinde) Oded Regev , "  Biz kafesler, hatalarla öğrenme, rastgele doğrusal kodlar ve kriptografi  " , Journal of the ACM , cilt.  56, n o  6, 2009, s.  34: 1-34: 40 ( DOI  10.1145 / 1568318.1568324 ).
  41. (in) Irit Dinur , "  Amplifikasyon boşluğuna göre PCP teoremi  ' , Journal of the ACM , cilt.  54, n o  3, 2007, s.  12
  42. (içinde) Robin A. Moser ve Gábor Tardos , "  yapıcı A kanıtı of the general Lovász Local Lemma  " , Journal of the ACM , cilt.  57, n o  2 2010, s.  11: 1-11: 15
  43. Andrei A. Bulatov, “  Sayma kısıtlaması memnuniyet probleminin karmaşıklığı  ”, Journal of the ACM , Association for Computing Machinery (ACM), cilt.  60, n o  5,2013, s.  1–41 ( ISSN  0004-5411 , DOI  10.1145 / 2528400 )
  44. Martin Dyer ve David Richerby , “  Sayma Kısıtlama Memnuniyet Problemi için Etkili Bir İkilik  ”, Society for Industrial & Applied Mathematics (SIAM) , cilt.  42, n o  3, 2013, s.  1245–1274 ( ISSN  0097-5397 , DOI  10.1137 / 100811258 )
  45. Jin-Yi Cai ve Xi Chen, “  Karmaşık Ağırlıklarla CSP Sayımı Karmaşıklığı  ” , Hesaplama Makineleri Derneği (ACM) , cilt.  64, n o  3, 22 Haziran 2017, s.  1–39 ( ISSN  0004-5411 , DOI  10.1145 / 2822891 )

Notlar

Notlar

  1. Fiyat sayfasının ilk paragrafları
  2. Jacques Stern , "  Antoine Joux, Prix Gödel 2013  ", 1024 - Fransa Bilişim Topluluğu Bülteni , n o  1,Eylül 2013, s.  107-110 ( çevrimiçi okuyun )
  3. EATCS web sitesinde: Ödül, Neumann'ın ölümünden kısa bir süre önce John von Neumann'a yazdığı bir mektupta keşfedilen, matematiksel mantığa yaptığı büyük katkılardan ve ilgisinden dolayı Kurt Gödel'in onuruna verilmiştir. P'ye karşı NP" sorusu.
  4. 2014 Gödel Ödülü'nün resmi duyurusu .
  5. Makale ve ödülle ilgili makale: Thore Husfeldt, “  Kişisel gerçeklik (Gödel Ödülü 2014)  ” [ arşiv du4 Mayıs 2015] ,2014( 30 Nisan 2015'te erişildi ) .
  6. "  2015 Gödel Ödülü  " , SIGACT'ta
  7. "  2016 Gödel Ödülü  " , EATCS'de
  8. "  2017 Gödel Ödülü  " ile, EATCS .
  9. "  2021 Gödel Ödülü atıf  "
(fr) Bu makale kısmen veya tamamen Wikipedia makalesinden alınmıştır İngilizce başlıklı "  Gödel Ödülü  " ( yazarların listesini görmek ) .

Şuna da bakın:

İlgili makale

Dış bağlantılar