Премія Геделя: відмінності між версіями
| [неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Виправлено джерел: 6; позначено як недійсні: 3. #IABot (v2.0beta14) |
→Лауреати: доповнення |
||
Рядок 82:
|-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>
|-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>
|}
| |||