Премія Геделя

Премія Геделя (англ. Gödel Prize) — щорічна премія за визначні праці у теоретичній інформатиці, яку присуджують з 1993 року організації ACM та EATCS (англ. European Association for Theoretical Computer Science). Її названо на честь австрійського логіка і математика Курта Геделя (1906—1978).

Премія Геделя англ. Gödel Prize
Тип	наукова нагородаd і computer science awardd
На честь:	Курт Гедель
Нагородження
Засновано:	1992
Нагороджені:
Категорія:Лауреати премії Геделя  (13)
Черговість
Премія Геделя у Вікісховищі

Премія включає у себе нагороду у розмірі 5000 доларів США. Премію вручають або на американському симпозіумі STOC (англ. Symposium on Theory of Computing), або на європейській конференції ICALP (англ. International Colloquium on Automata, Languages and Programming). До участі приймають усі роботи, час від першої публікації яких не перевищує 14 років.

Лауреати

Курт Гедель (1925)

Рік	Імена	За що	Рік публікації
1993	Ласло Бабай, Шафі Ґолдвассер, Сільвіо Мікалі, Шломо Моран та Чарльз Рекоф	за розробку інтерактивних систем доведення	1988[праця 1], 1989[праця 2]
1994	Йохан Хостад	за експоненційну нижню межу розміру логічних циклів з константною глибиною (для функції парності).	1989[праця 3]
1995	Ніл Іммерман та Роберт Селепчені	за теорему Іммермана-Селепчені стосовно недетермінованої просторової складності	1988[праця 4], 1988[праця 5]
1996	Марк Джерум та Елістер Сінклер	за роботу над ланцюгами Маркова і апроксимацією перманента	1989[праця 6], 1989[праця 7]
1997	Джозеф Галперн та Йорам Мосес	за визначення формального запису «знань» у розподілених середовищах	1990[праця 8]
1998	Сеіносуке Тода	за теорему Тода, яка показала зв'язок між обчисленими розв'язками (PP) і чергуванням кванторів (PH)	1991[праця 9]
1999	Пітер Шор	за алгоритм Шора для факторизації чисел за поліноміальний час на квантовому комп'ютері	1997[праця 10]
2000	Моше Варді та П'єр Волпер	за роботу над перевіркою моделей із скінченними автоматами	1994[праця 11]
2001	Сенджев Арора, Уріель Фейґе, Шафі Ґолдвассер, Ларстен Лунд, Ласло Ловас, Раджів Мотвані, Шмуель Сафра, Мадху Судан та Маріо Сеґеді	за PCP-теорему та її застосування до складності апроксимації	1996[праця 12], 1998[праця 13], 1998[праця 14]
2002	Жеро Сенізерґ	за доведення того, що еквівалентність детермінованих стекових автоматів є розв'язуваною	2001[праця 15]
2003	Йоув Фруенд та Роберт Шапіро	за алгоритм AdaBoost	1997[праця 16]
2004	Моріс Герлігу, Майкл Сакс, Нір Шавіт та Фотіос Загароґлоу	за застосування топології до теорії розподілених обчислень	1999[праця 17], 2000[праця 18]
2005	Ноґа Алон, Йоссі Матіас та Mario Szegedy	за їхній фундаментальний внесок до потокових алгоритмів	1999[праця 19]
2006	Маніндра Аґравал, Нірадж Каяль, Нітін Саксена	за тест простоти AKS	2004[праця 20]
2007	Олександр Разборов, Стівен Редік	за природні доведення	1997[праця 21]
2008	Шанг-Хуа Тенг, Деніель Спілмен	за згладжений аналіз алгоритмів	2004[праця 22]
2009	Омер Реінгольд, Саліл Вадген, Аві Віґдерсон	за зигзаговий добуток графів та ненапрямлену зв'язність у логарифмічному просторі	2002[праця 23], 2008[праця 24]
2010	Сенджев Арора, Джозеф Мітчел	за їхнє одночасне відкриття поліноміальної апроксимаційної схеми для евклідової задачі комівояжера (ETSP)	1998[праця 25], 1999[праця 26]
2011	Йохан Хастад	за покращення PCP-теореми за допомогою нових імовірнісних верифікаторів, що дозволяють перевірити належність слова до NP-мови, прочитавши не більше ніж три біти з відповідного доведення	2001[праця 27]
2012	Elias Koutsoupias[de], Христос Пападімітріу, Noam Nisan, Amir Ronen[de], Tim Roughgarden і Ева Тардош	за закладення основ алгоритмічної теорії ігор[en][1]	2009,[праця 28] 2002,[праця 29] 2001[праця 30]
2013	Ден Бонех, Matthew K. Franklin, and Antoine Joux	за багатосторонній протокол Діффі-Геллмана та схему Боєна-Франкліна[en] в криптографії[2]	2003,[праця 31] 2004[праця 32]
2014	Ronald Fagin, Amnon Lotem[fr], and Moni Naor	за оптимальні алгоритми агрегації для проміжного програмного забезпечення[3]	2003,[праця 33]
2015	Деніел Спілмен, Shanghua Teng	за низку робіт з практично-лінійних розв'язувачів Лапласа[4]	2011[праця 34] 2013[праця 35] 2014[праця 36]
2016	Stephen Brookes and Peter W. O'Hearn	за винахід Паралельної логіки розділення[en]	2007[праця 37], 2007[праця 38]
2017[5]	Cynthia Dwork, Frank McSherry[fr], Kobbi Nissim, та Adam D. Smith[fr]	за дослідження диференційної приватності	2006[праця 39]
2018[6]	Oded Regev	за введення у розгляд задачи навчання з помилками[en]	2009[праця 40]
2019[7]	Іріт Дінур	за нове доведення PCP-теореми	2007[праця 41]

Переможні праці

1. Babai, László; Moran, Shlomo (1988), Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class (PDF), Journal of Computer and System Sciences, Boston, MA: Academic Press, 36 (2): 254—276, doi:10.1016/0022-0000(88)90028-1, ISSN 0022-0000, архів оригіналу (PDF) за 6 липня 2011, процитовано 17 грудня 2009
2. Goldwasser, S.; Micali, S.; Rackoff, C. (1989), The knowledge complexity of interactive proof systems (PDF), SIAM Journal on Computing, Philadelphia: Society for Industrial and Applied Mathematics, 18 (1): 186—208, doi:10.1137/0218012, ISSN 1095-7111, архів оригіналу (PDF) за 27 вересня 2011, процитовано 17 грудня 2009
3. Håstad, Johan (1989), Almost Optimal Lower Bounds for Small Depth Circuits, у Micali, Silvio (ред.), Randomness and Computation (PDF), Advances in Computing Research, т. 5, JAI Press, с. 6—20, ISBN 0892328967, архів оригіналу (PDF) за 22 лютого 2012, процитовано 17 грудня 2009
4. Immerman, Neil (1988), Nondeterministic space is closed under complementation (PDF), SIAM Journal on Computing, Philadelphia: Society for Industrial and Applied Mathematics, 17 (5): 935—938, doi:10.1137/0217058, ISSN 1095-7111
5. Szelepcsényi, R. (1988), The method of forced enumeration for nondeterministic automata, Acta Informatica, Springer-Verlag New York, Inc., 26 (3): 279—284, doi:10.1007/BF00299636
6. Sinclair, A.; Jerrum, M. (1989), Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation, Elsevier, 82 (1): 93—133, doi:10.1016/0890-5401(89)90067-9, ISSN 0890-5401
7. Jerrum, M.; Sinclair, Alistair (1989), Approximating the permanent, SIAM Journal on Computing, Philadelphia: Society for Industrial and Applied Mathematics, 18 (6): 1149—1178, doi:10.1137/0218077, ISSN 1095-7111
8. Halpern, Joseph; Moses, Yoram (1990), Knowledge and common knowledge in a distributed environment, Journal of the ACM, 37 (3): 549—587, doi:10.1145/79147.79161
9. Toda, Seinosuke (1991), PP is as hard as the polynomial-time hierarchy (PDF), SIAM Journal on Computing, Philadelphia: Society for Industrial and Applied Mathematics, 20 (5): 865—877, doi:10.1137/0220053, ISSN 1095-7111, архів оригіналу (PDF) за 21 лютого 2007, процитовано 17 грудня 2009
10. Shor, Peter W. (1997), Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (PDF), SIAM Journal on Computing, Philadelphia: Society for Industrial and Applied Mathematics, 26 (5): 1484—1509, doi:10.1137/S0097539795293172, ISSN 1095-7111^{[недоступне посилання з квітня 2019]}
11. Vardi, Moshe Y.; Wolper, Pierre (1994), Reasoning about infinite computations (PDF), Information and Computation, Boston, MA: Academic Press, 115 (1): 1—37, doi:10.1006/inco.1994.1092, ISSN 0890-5401, архів оригіналу (PDF) за 25 серпня 2011, процитовано 17 грудня 2009
12. Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (1996), Interactive proofs and the hardness of approximating cliques (PDF), Journal of the ACM, ACM, 43 (2): 268—292, doi:10.1145/226643.226652, ISSN 0004-5411, архів оригіналу (PDF) за 10 червня 2011, процитовано 17 грудня 2009
13. Arora, Sanjeev; Safra, Shmuel (1998), Probabilistic checking of proofs: a new characterization of NP (PDF), Journal of the ACM, ACM, 45 (1): 70—122, doi:10.1145/273865.273901, ISSN 0004-5411, архів оригіналу (PDF) за 10 червня 2011, процитовано 17 грудня 2009
14. Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), Proof verification and the hardness of approximation problems (PDF), Journal of the ACM, ACM, 45 (3): 501—555, doi:10.1145/278298.278306, ISSN 0004-5411, архів оригіналу (PDF) за 10 червня 2011, процитовано 17 грудня 2009
15. Sénizergues, Géraud (2001), L(A) = L(B)? decidability results from complete formal systems, Theor. Comput. Sci., Essex, UK: Elsevier Science Publishers Ltd., 251 (1): 1—166, doi:10.1016/S0304-3975(00)00285-1, ISSN 0304-3975
16. Freund, Y.; Schapire, R.E. (1997), A decision-theoretic generalization of on-line learning and an application to boosting (PDF), Journal of Computer and System Sciences, Elsevier, 55 (1): 119—139, doi:10.1006/jcss.1997.1504, ISSN 1090-2724
17. Herlihy, Maurice; Shavit, Nir (1999), The topological structure of asynchronous computation (PDF), Journal of the ACM, 46 (6): 858—923, doi:10.1145/331524.331529. Gödel prize lecture
18. Saks, Michael; Zaharoglou, Fotios (2000), Wait-free k-set agreement is impossible: The topology of public knowledge", SIAM Journal on Computing, 29 (5): 1449—1483, doi:10.1137/S0097539796307698
19. Alon, Noga; Matias, Yossi; Szegedy, Mario (1999), The space complexity of approximating the frequency moments (PDF), Journal of Computer and System Sciences, 58 (1): 137—147, doi:10.1006/jcss.1997.1545. First presented at the Symposium on Theory of Computing (STOC) in 1996.
20. Agrawal, M.; Kayal, N.; Saxena, N. (2004), PRIMES is in P (PDF), Annals of Mathematics, 160: 781—793, doi:10.4007/annals.2004.160.781, ISSN 0003-486X, архів оригіналу (PDF) за 7 червня 2011, процитовано 17 грудня 2009
21. Razborov, Alexander A.; Rudich, Steven (1997), Natural proofs, Journal of Computer and System Sciences, Boston, MA: Academic Press, 55 (1): 24—35, doi:10.1006/jcss.1997.1494, ISSN 0022-0000
22. Spielman, Daniel A.; Teng, Shang-Hua (2004), Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time (PDF), J. ACM, ACM, 51 (3): 385—463, ISSN 0004-5411^{[недоступне посилання з квітня 2019]}
23. Reingold, Omer; Vadhan, Salil; Wigderson, Avi (2002), Entropy waves, the zig-zag graph product, and new constant-degree expanders (PDF), Annals of Mathematics, 155 (1): 157—187, doi:10.2307/3062153, ISSN 0003-486X, MR1888797^{[недоступне посилання з квітня 2019]}
24. Reingold, Omer (2008), Undirected connectivity in log-space, J. ACM, ACM, 55 (4): 1—24, ISSN 0004-5411, архів оригіналу за 12 червня 2011, процитовано 17 грудня 2009
25. Arora, Sanjeev (1998), Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM, ACM, 45 (5): 753—782, doi:10.1145/290179.290180, ISSN 0004-5411
26. Mitchell, Joseph S. B. (1999), Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems, SIAM Journal on Computing, Philadelphia: Society for Industrial and Applied Mathematics, 28 (4): 1298—1309, doi:10.1137/S0097539796309764, ISSN 1095-7111
27. Hastad, Johan (2001), Some optimal inapproximability results, Journal of the ACM, ACM, 48 (4): 798—859, doi:10.1145/502090.502098, ISSN 0004-5411
28. Koutsoupias, Elias; Papadimitriou, Christos (2009). Worst-case equilibria. Computer Science Review. 3 (2): 65—69. doi:10.1016/j.cosrev.2009.04.003.
29. Roughgarden, Tim; Tardos, Éva (2002). How bad is selfish routing?. Journal of the ACM. 49 (2): 236—259. CiteSeerX 10.1.1.147.1081. doi:10.1145/506147.506153.
30. Nisan, Noam; Ronen, Amir (2001). Algorithmic Mechanism Design. Games and Economic Behavior. 35 (1–2): 166—196. CiteSeerX 10.1.1.21.1731. doi:10.1006/game.1999.0790.
31. Boneh, Dan; Franklin, Matthew (2003). Identity-based encryption from the Weil pairing. SIAM Journal on Computing. 32 (3): 586—615. CiteSeerX 10.1.1.66.1131. doi:10.1137/S0097539701398521. MR 2001745.
32. Joux, Antoine (2004). A one round protocol for tripartite Diffie-Hellman. Journal of Cryptology. 17 (4): 263—276. doi:10.1007/s00145-004-0312-y. MR 2090557.
33. Fagin, Ronald; Lotem, Amnon; Naor, Moni (2003). Optimal aggregation algorithms for middleware. Journal of Computer and System Sciences. 66 (4): 614—656. arXiv:cs/0204046. doi:10.1016/S0022-0000(03)00026-6.
34. Spielman, Daniel A.; Teng, Shang-Hua (2011). Spectral Sparsification of Graphs. SIAM Journal on Computing. 40 (4): 981—1025. arXiv:0808.4134. doi:10.1137/08074489X. ISSN 0097-5397.
35. Spielman, Daniel A.; Teng, Shang-Hua (2013). A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning. SIAM Journal on Computing. 42 (1): 1—26. arXiv:0809.3232. doi:10.1137/080744888. ISSN 0097-5397.
36. Spielman, Daniel A.; Teng, Shang-Hua (2014). Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems. SIAM Journal on Matrix Analysis and Applications. 35 (3): 835—885. arXiv:cs/0607105. doi:10.1137/090771430. ISSN 0895-4798.
37. Brookes, Stephen (2007). A Semantics for Concurrent Separation Logic (PDF). Theoretical Computer Science. 375 (1–3): 227—270. doi:10.1016/j.tcs.2006.12.034.
38. O'Hearn, Peter (2007). Resources, Concurrency and Local Reasoning (PDF). Theoretical Computer Science. 375 (1–3): 271—307. doi:10.1016/j.tcs.2006.12.035.
39. Dwork, Cynthia; McSherry, Frank; Nissim, Kobbi; Smith, Adam (2006). Halevi, Shai; Rabin, Tal (ред.). Calibrating Noise to Sensitivity in Private Data Analysis. Theory of Cryptography (TCC). Lecture Notes in Computer Science. Т. 3876. Springer-Verlag. с. 265—284. doi:10.1007/11681878_14. ISBN 978-3-540-32731-8.
40. Regev, Oded (2009). On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM. 56 (6): 1—40. CiteSeerX 10.1.1.215.3543. doi:10.1145/1568318.1568324.
41. Dinur, Irit (2007). The PCP theorem by gap amplification. Journal of the ACM. 54 (3).