Відмінності між версіями «Премія Геделя»

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
[неперевірена версія][неперевірена версія]
(Виправлено джерел: 6; позначено як недійсні: 3. #IABot (v2.0beta14))
(→‎Лауреати: доповнення)
 
Рядок 82: Рядок 82:
 
|-valign="top"
 
|-valign="top"
 
|2011 ||[[Йохан Хастад]]|| за покращення [[PCP-теорема|PCP-теореми]] за допомогою нових імовірнісних верифікаторів, що дозволяють перевірити належність слова до [[NP]]-[[Формальна мова|мови]], прочитавши не більше ніж три біти з відповідного доведення || 2001<ref group="праця">{{Citation | last1=Hastad | first1=Johan | title=Some optimal inapproximability results | publisher=ACM | doi=10.1145/502090.502098 | year=2001 | journal=Journal of the ACM | issn=0004-5411 | volume=48 | issue=4 | pages=798-859}}</ref>
 
|2011 ||[[Йохан Хастад]]|| за покращення [[PCP-теорема|PCP-теореми]] за допомогою нових імовірнісних верифікаторів, що дозволяють перевірити належність слова до [[NP]]-[[Формальна мова|мови]], прочитавши не більше ніж три біти з відповідного доведення || 2001<ref group="праця">{{Citation | last1=Hastad | first1=Johan | title=Some optimal inapproximability results | publisher=ACM | doi=10.1145/502090.502098 | year=2001 | journal=Journal of the ACM | issn=0004-5411 | volume=48 | issue=4 | pages=798-859}}</ref>
  +
|-valign="top"
  +
|2012 || {{Нп|Elias Koutsoupias||de|}}, [[Христос Пападімітріу]], [[Noam Nisan]], {{Нп|Amir Ronen||de|}}, [[Tim Roughgarden]] and [[Éva Tardos]] || за закладення основ {{Нп|алгоритмічна теорія ігор|алгоритмічної теорії ігор||algorithmic game theory}}<ref name=sigact-2012>{{cite news|title=Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory|url=http://www.acm.org/press-room/news-releases/2012/goedel-prize-2012|accessdate=16 May 2012|date=16 May 2012|deadurl=yes|archiveurl=https://web.archive.org/web/20130718154540/http://www.acm.org/press-room/news-releases/2012/goedel-prize-2012|archivedate=18 July 2013|df=}}</ref> || 2009,<ref group=праця>{{cite journal|last=Koutsoupias|first=Elias|author2=Papadimitriou, Christos|title=Worst-case equilibria|journal=Computer Science Review|year=2009|volume=3|issue=2|pages=65–69|doi=10.1016/j.cosrev.2009.04.003}}</ref> 2002,<ref group = "праця">{{cite journal|last=Roughgarden|first=Tim|author2=Tardos, Éva|title=How bad is selfish routing?|journal=Journal of the ACM|year=2002|volume=49|issue=2|pages=236–259|doi=10.1145/506147.506153|citeseerx=10.1.1.147.1081}}</ref> 2001<ref group="праця">{{cite journal|last=Nisan|first=Noam|author2=Ronen, Amir|title=Algorithmic Mechanism Design|journal=Games and Economic Behavior|year=2001|volume=35|issue=1–2|pages=166–196|doi=10.1006/game.1999.0790|citeseerx=10.1.1.21.1731}}</ref>
  +
|-valign="top"
  +
|2013 || [[Ден Бонех]], [[Matthew K. Franklin]], and [[Antoine Joux]] || за багатосторонній [[протокол Діффі-Геллмана]] та {{Нп|Схема Боєна-Франкліна|схему Боєна-Франкліна||Boneh–Franklin scheme}} в криптографії<ref>[http://www.acm.org/press-room/news-releases/2013/goedel-prize-13/ ACM Group Presents Gödel Prize for Advances in Cryptography: Three Computer Scientists Cited for Innovations that Improve Security] {{webarchive|url=https://web.archive.org/web/20130601191333/http://www.acm.org/press-room/news-releases/2013/goedel-prize-13 |date=2013-06-01 }}, [[Association for Computing Machinery]], May 29, 2013.</ref> || 2003,<ref group="праця">{{cite journal | last1 = Boneh | first1 = Dan | last2 = Franklin | first2 = Matthew | doi = 10.1137/S0097539701398521 | issue = 3 | journal = SIAM Journal on Computing | mr = 2001745 | pages = 586–615 | title = Identity-based encryption from the Weil pairing | volume = 32 | year = 2003| citeseerx = 10.1.1.66.1131 }}</ref>
  +
2004<ref group="праця">{{cite journal | last = Joux | first = Antoine | doi = 10.1007/s00145-004-0312-y | issue = 4 | journal = Journal of Cryptology | mr = 2090557 | pages = 263–276 | title = A one round protocol for tripartite Diffie-Hellman | volume = 17 | year = 2004}}</ref>
  +
|-valign="top"
  +
|2014 || [[Ronald Fagin]], {{Нп|Amnon Lotem||fr|}}, and [[Moni Naor]] || за оптимальні алгоритми агрегації для проміжного програмного забезпечення<ref>[https://eatcs.org/index.php/component/content/article/1-news/1908-goedel-prize-2014 Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources], [[Association for Computing Machinery]], April 30, 2014.</ref> || 2003,<ref group="праця">{{cite journal | last1 = Fagin | first1 = Ronald | last2 = Lotem | first2 = Amnon | last3 = Naor | first3 = Moni | doi = 10.1016/S0022-0000(03)00026-6 | issue = 4 | journal = Journal of Computer and System Sciences | pages = 614–656 | title = Optimal aggregation algorithms for middleware | volume = 66 | year = 2003| arxiv = cs/0204046 }}</ref>
  +
|-valign="top"
  +
|2015 || [[Daniel Spielman]], [[Shanghua Teng]]
  +
|| за низку робіт з практично-лінійних розв'язувачів Лапласа<ref>[http://www.sigact.org/Prizes/Godel/citation2015.pdf 2015 Gödel Prize announcement] {{Webarchive|url=https://web.archive.org/web/20171209021752/http://www.sigact.org/Prizes/Godel/citation2015.pdf |date=2017-12-09 }} by [[Association for Computing Machinery]].</ref> ||
  +
2011<ref group="праця" name="SpielmanTeng2011">{{cite journal|last1=Spielman|first1=Daniel A.|last2=Teng|first2=Shang-Hua|title=Spectral Sparsification of Graphs|journal=SIAM Journal on Computing|volume=40|issue=4|year=2011|pages=981–1025|issn=0097-5397|doi=10.1137/08074489X|arxiv=0808.4134}}</ref>
  +
2013<ref group="праця" name="SpielmanTeng2013">{{cite journal|last1=Spielman|first1=Daniel A.|last2=Teng|first2=Shang-Hua|title=A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning|journal=SIAM Journal on Computing|volume=42|issue=1|year=2013|pages=1–26|issn=0097-5397|doi=10.1137/080744888|arxiv=0809.3232}}</ref>
  +
2014<ref group="праця" name="SpielmanTeng2014">{{cite journal|last1=Spielman|first1=Daniel A.|last2=Teng|first2=Shang-Hua|title=Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems|journal=SIAM Journal on Matrix Analysis and Applications|volume=35|issue=3|year=2014|pages=835–885|issn=0895-4798|doi=10.1137/090771430|arxiv=cs/0607105}}</ref>
  +
|-
  +
|2016
  +
|Stephen Brookes and [[Peter O'Hearn|Peter W. O'Hearn]]
  +
|за винахід {{Нп|Логіка розділення|Паралельної логіки розділення||Separation_logic#Concurrent_separation_logic}}
  +
|2007<ref group="праця">{{cite journal|last1=Brookes|first1=Stephen|title=A Semantics for Concurrent Separation Logic|journal=Theoretical Computer Science|date=2007|volume=375|issue=1–3|pages=227–270|doi=10.1016/j.tcs.2006.12.034|url=http://www.cs.cmu.edu/~brookes/papers/seplogicrevisedfinal.pdf}}</ref>, 2007<ref group="праця">{{cite journal|last1=O'Hearn|first1=Peter|title=Resources, Concurrency and Local Reasoning|journal=Theoretical Computer Science|date=2007|volume=375|issue=1–3|pages=271–307|doi=10.1016/j.tcs.2006.12.035|url=http://www.cs.ucl.ac.uk/staff/p.ohearn/papers/concurrency.pdf}}</ref>
  +
|-
  +
|2017<ref name=Godël2017>{{cite web|title=2017 Gödel Prize|url=https://www.eatcs.org/index.php/component/content/article/1-news/2450-2017-godel-prize|website=European Association for Theoretical Computer Science|publisher=EATCS|accessdate=29 March 2017}}</ref>
  +
|[[Cynthia Dwork]], {{Нп|Frank McSherry||fr|}}, [[Kobbi Nissim]], та {{Нп|Adam D. Smith||fr|}}
  +
|за дослідження [[Диференційна приватність|диференційної приватності]]
  +
|2006<ref group="праця">{{cite conference |title=Calibrating Noise to Sensitivity in Private Data Analysis |first1=Cynthia |last1=Dwork |first2=Frank |last2= McSherry |first3=Kobbi |last3=Nissim |first4=Adam |last4=Smith| year=2006 |conference=Theory of Cryptography (TCC)| editor-last1 = Halevi| editor-first1 = Shai| editor-last2=Rabin| editor-first2=Tal|series=Lecture Notes in Computer Science|volume= 3876 |publisher= Springer-Verlag |pages=265–284 |isbn=978-3-540-32731-8 |doi=10.1007/11681878_14}}</ref>
  +
|-
  +
|2018<ref name=Godël2018>{{cite web|title=2018 Gödel Prize citation|url=http://eatcs.org/index.php/component/content/article/1-news/2670-2018-godel-prize}}</ref>
  +
| [[Oded Regev (Computer Scientist)|Oded Regev]]
  +
|за введення у розгляд задачи {{Нп|навчання з помилками|||Learning with errors}}
  +
|2009<ref group="праця" name="Regev2009">{{cite journal|last1=Regev|first1=Oded|title=On lattices, learning with errors, random linear codes, and cryptography|journal=Journal of the ACM|volume=56|issue=6|pages=1–40|url=https://dl.acm.org/citation.cfm?id=1568324|doi=10.1145/1568318.1568324|year=2009|citeseerx=10.1.1.215.3543}}</ref>
  +
|-
  +
|2019<ref name=Godël2019>{{cite web|title=2019 Gödel Prize citation|url=http://eatcs.org/index.php/component/content/article/1-news/2807-2019-03-12-20-31-09}}</ref>
  +
| [[Іріт Дінур]]
  +
|за нове доведення [[PCP-теорема|PCP-теореми]]
  +
|2007<ref group="праця" name="Dinur2007">{{cite journal|last1=Dinur|first1=Irit|title=The PCP theorem by gap amplification|journal=Journal of the ACM|volume=54|issue=3|url=https://dl.acm.org/citation.cfm?id=1236459|year=2007}}</ref>
 
|}
 
|}
   

Поточна версія на 18:24, 14 липня 2019

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

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

Лауреати[ред. | ред. код]

Рік Імена За що Рік публікації
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 and Éva Tardos за закладення основ алгоритмічної теорії ігор[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 Daniel Spielman, 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. Journal of Computer and System Sciences (Boston, MA: Academic Press) 36 (2): 254–276. ISSN 0022-0000. doi:10.1016/0022-0000(88)90028-1. 
  2. Goldwasser, S.; Micali, S.; Rackoff, C. (1989). The knowledge complexity of interactive proof systems. SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 18 (1): 186–208. ISSN 1095-7111. doi:10.1137/0218012. 
  3. Håstad, Johan (1989). Almost Optimal Lower Bounds for Small Depth Circuits. У Micali, Silvio. Randomness and Computation. Advances in Computing Research 5. JAI Press. с. 6–20. ISBN 0892328967. Архів оригіналу за 22 лютий 2012. Процитовано 17 грудень 2009. 
  4. Immerman, Neil (1988). Nondeterministic space is closed under complementation. SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 17 (5): 935–938. ISSN 1095-7111. doi:10.1137/0217058. 
  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. ISSN 0890-5401. doi:10.1016/0890-5401(89)90067-9. 
  7. Jerrum, M.; Sinclair, Alistair (1989). Approximating the permanent. SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 18 (6): 1149–1178. ISSN 1095-7111. doi:10.1137/0218077. 
  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. SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 20 (5): 865–877. ISSN 1095-7111. doi:10.1137/0220053. 
  10. Shor, Peter W. (1997). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 26 (5): 1484–1509. ISSN 1095-7111. doi:10.1137/S0097539795293172. [недоступне посилання з квітень 2019]
  11. Vardi, Moshe Y.; Wolper, Pierre (1994). Reasoning about infinite computations. Information and Computation (Boston, MA: Academic Press) 115 (1): 1–37. ISSN 0890-5401. doi:10.1006/inco.1994.1092. Архів оригіналу за 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. Journal of the ACM (ACM) 43 (2): 268–292. ISSN 0004-5411. doi:10.1145/226643.226652. 
  13. Arora, Sanjeev; Safra, Shmuel (1998). Probabilistic checking of proofs: a new characterization of NP. Journal of the ACM (ACM) 45 (1): 70–122. ISSN 0004-5411. doi:10.1145/273865.273901. Архів оригіналу за 10 червень 2011. Процитовано 17 грудень 2009. 
  14. Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998). Proof verification and the hardness of approximation problems. Journal of the ACM (ACM) 45 (3): 501–555. ISSN 0004-5411. doi:10.1145/278298.278306. Архів оригіналу за 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. ISSN 0304-3975. doi:10.1016/S0304-3975(00)00285-1. 
  16. Freund, Y.; Schapire, R.E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences (Elsevier) 55 (1): 119–139. ISSN 1090-2724. doi:10.1006/jcss.1997.1504. 
  17. Herlihy, Maurice; Shavit, Nir (1999). The topological structure of asynchronous computation. 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. 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. Annals of Mathematics 160: 781–793. ISSN 0003-486X. doi:10.4007/annals.2004.160.781. Архів оригіналу за 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. ISSN 0022-0000. doi:10.1006/jcss.1997.1494. 
  22. Spielman, Daniel A.; Teng, Shang-Hua (2004). Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. 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. Annals of Mathematics 155 (1): 157–187. ISSN 0003-486X. doi:10.2307/3062153. MR1888797. [недоступне посилання з квітень 2019]
  24. Reingold, Omer (2008). Undirected connectivity in log-space. J. ACM (ACM) 55 (4): 1–24. ISSN 0004-5411. Архів оригіналу за 2011-06-12. Процитовано 2009-12-17. 
  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. ISSN 0004-5411. doi:10.1145/290179.290180. 
  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. ISSN 1095-7111. doi:10.1137/S0097539796309764. 
  27. Hastad, Johan (2001). Some optimal inapproximability results. Journal of the ACM (ACM) 48 (4): 798–859. ISSN 0004-5411. doi:10.1145/502090.502098. 
  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. doi:10.1145/506147.506153.  Проігноровано невідомий параметр |citeseerx= (довідка)
  30. Nisan, Noam; Ronen, Amir (2001). Algorithmic Mechanism Design. Games and Economic Behavior 35 (1–2): 166–196. doi:10.1006/game.1999.0790.  Проігноровано невідомий параметр |citeseerx= (довідка)
  31. Boneh, Dan; Franklin, Matthew (2003). Identity-based encryption from the Weil pairing. SIAM Journal on Computing 32 (3): 586–615. MR 2001745. doi:10.1137/S0097539701398521.  Проігноровано невідомий параметр |citeseerx= (довідка)
  32. Joux, Antoine (2004). A one round protocol for tripartite Diffie-Hellman. Journal of Cryptology 17 (4): 263–276. MR 2090557. doi:10.1007/s00145-004-0312-y. 
  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. ISSN 0097-5397. arXiv:0808.4134. doi:10.1137/08074489X. 
  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. ISSN 0097-5397. arXiv:0809.3232. doi:10.1137/080744888. 
  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. ISSN 0895-4798. arXiv:cs/0607105. doi:10.1137/090771430. 
  37. Brookes, Stephen (2007). A Semantics for Concurrent Separation Logic. 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. 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. ISBN 978-3-540-32731-8. doi:10.1007/11681878_14. 
  40. Regev, Oded (2009). On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM 56 (6): 1–40. doi:10.1145/1568318.1568324.  Проігноровано невідомий параметр |citeseerx= (довідка)
  41. Dinur, Irit (2007). The PCP theorem by gap amplification. Journal of the ACM 54 (3). 

Посилання[ред. | ред. код]

  • Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory. 16 May 2012. Архів оригіналу за 18 July 2013. Процитовано 16 May 2012. 
  • ACM Group Presents Gödel Prize for Advances in Cryptography: Three Computer Scientists Cited for Innovations that Improve Security Архівовано 2013-06-01 у Wayback Machine., Association for Computing Machinery, May 29, 2013.
  • Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources, Association for Computing Machinery, April 30, 2014.
  • 2015 Gödel Prize announcement Архівовано 2017-12-09 у Wayback Machine. by Association for Computing Machinery.
  • 2017 Gödel Prize. European Association for Theoretical Computer Science. EATCS. Процитовано 29 March 2017. 
  • 2018 Gödel Prize citation. 
  • 2019 Gödel Prize citation.