Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Премія Геделя англ Gödel Prize щорічна премія за визначні праці у теоретичній інформатиці що присуджується з 1993 року о

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

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

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

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

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

Лауреати

image
Курт Гедель (1925)
Рік Імена За що Рік публікації
1993 Ласло Бабай, Шафі Ґолдвассер, Сільвіо Мікалі, та за розробку 1988, 1989
1994 за експонентну нижню межу з константною глибиною (для ). 1989
1995 та за стосовно недетермінованої просторової складності 1988, 1988
1996 та за роботу над ланцюгами Маркова і апроксимацією перманента 1989, 1989
1997 та за визначення формального запису «знань» у розподілених середовищах 1990
1998 за , яка показала зв'язок між обчисленими розв'язками () і чергуванням кванторів () 1991
1999 Пітер Шор за алгоритм Шора для факторизації чисел за поліноміальний час на квантовому комп'ютері 1997
2000 Моше Варді та за роботу над перевіркою моделей із скінченними автоматами 1994
2001 , , Шафі Ґолдвассер, , Ласло Ловас, , , та за PCP-теорему та її застосування до складності апроксимації 1996, 1998, 1998
2002 за доведення того, що еквівалентність є 2001
2003 та Роберт Шапіро за алгоритм 1997
2004 , , та за застосування топології до теорії розподілених обчислень 1999, 2000
2005 Ноґа Алон, та за їхній фундаментальний внесок до потокових алгоритмів 1999
2006 , , за тест простоти AKS 2004
2007 , за 1997
2008 , за алгоритмів 2004
2009 , , Аві Віґдерсон за графів та у логарифмічному просторі 2002, 2008
2010 , за їхнє одночасне відкриття для евклідової задачі комівояжера (ETSP) 1998,

1999

2011 за покращення PCP-теореми за допомогою нових імовірнісних верифікаторів, що дозволяють перевірити належність слова до NP-мови, прочитавши не більше ніж три біти з відповідного доведення 2001
2012 [de], Христос Пападімітріу, , [de], і Ева Тардош за закладення основ [en] 2009, 2002, 2001
2013 Ден Бонех, , and за багатосторонній протокол Діффі-Геллмана та [en] в криптографії 2003,

2004

2014 , [fr], and за оптимальні алгоритми агрегації для проміжного програмного забезпечення 2003,
2015 Деніел Спілмен, за низку робіт з практично-лінійних розв'язувачів Лапласа

2011 2013 2014

2016 Stephen Brookes and за винахід [en] 2007, 2007
2017 , [fr], , та [fr] за дослідження диференційної приватності 2006
2018 за введення у розгляд задачи [en] 2009
2019 Іріт Дінур за нове доведення PCP-теореми 2007

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

  1. Babai, László; Moran, Shlomo (1988), (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), (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 (ред.), (PDF), Advances in Computing Research, т. 5, JAI Press, с. 6—20, ISBN , архів оригіналу (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), (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), (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
  13. Arora, Sanjeev; Safra, Shmuel (1998), (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), (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), (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), , 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 .
  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).

Примітки

  1. . 16 травня 2012. Архів оригіналу за 18 July 2013. Процитовано 16 травня 2012.
  2. 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.
  3. Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources, Association for Computing Machinery, April 30, 2014.
  4. 2015 Gödel Prize announcement [ 2017-12-09 у Wayback Machine.] by Association for Computing Machinery.
  5. 2017 Gödel Prize. European Association for Theoretical Computer Science. EATCS. Процитовано 29 березня 2017.
  6. 2018 Gödel Prize citation.
  7. 2019 Gödel Prize citation.

Посилання

  • Офіційний сайт зі списком лауреатів

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Premiya Gedelya angl Godel Prize shorichna premiya za viznachni praci u teoretichnij informatici sho prisudzhuyetsya z 1993 roku organizaciyami ACM ta EATCS angl European Association for Theoretical Computer Science Nazvana na chest avstrijskogo logika i matematika Kurta Gedelya 1906 1978 Premiya Gedelya angl Godel PrizeKrayina SShATip d i dNa chest Kurt GedelNagorodzhennyaZasnovano 1992Nagorodzheni Kategoriya Laureati premiyi Gedelya 13 Chergovist Premiya Gedelya u Vikishovishi Premiya vklyuchaye u sebe nagorodu u rozmiri 5000 dolariv SShA Premiya vruchayetsya abo na amerikanskomu simpoziumi STOC angl Symposium on Theory of Computing abo na yevropejskij konferenciyi ICALP angl International Colloquium on Automata Languages and Programming Do uchasti prijmayutsya usi roboti chas vid pershoyi publikaciyi yakih ne perevishuye 14 rokiv LaureatiKurt Gedel 1925 Rik Imena Za sho Rik publikaciyi1993 Laslo Babaj Shafi Goldvasser Silvio Mikali ta za rozrobku 1988 19891994 za eksponentnu nizhnyu mezhu z konstantnoyu glibinoyu dlya 19891995 ta za stosovno nedeterminovanoyi prostorovoyi skladnosti 1988 19881996 ta za robotu nad lancyugami Markova i aproksimaciyeyu permanenta 1989 19891997 ta za viznachennya formalnogo zapisu znan u rozpodilenih seredovishah 19901998 za yaka pokazala zv yazok mizh obchislenimi rozv yazkami i cherguvannyam kvantoriv 19911999 Piter Shor za algoritm Shora dlya faktorizaciyi chisel za polinomialnij chas na kvantovomu komp yuteri 19972000 Moshe Vardi ta za robotu nad perevirkoyu modelej iz skinchennimi avtomatami 19942001 Shafi Goldvasser Laslo Lovas ta za PCP teoremu ta yiyi zastosuvannya do skladnosti aproksimaciyi 1996 1998 19982002 za dovedennya togo sho ekvivalentnist ye 20012003 ta Robert Shapiro za algoritm 19972004 ta za zastosuvannya topologiyi do teoriyi rozpodilenih obchislen 1999 20002005 Noga Alon ta za yihnij fundamentalnij vnesok do potokovih algoritmiv 19992006 za test prostoti AKS 20042007 za 19972008 za algoritmiv 20042009 Avi Vigderson za grafiv ta u logarifmichnomu prostori 2002 20082010 za yihnye odnochasne vidkrittya dlya evklidovoyi zadachi komivoyazhera ETSP 1998 19992011 za pokrashennya PCP teoremi za dopomogoyu novih imovirnisnih verifikatoriv sho dozvolyayut pereviriti nalezhnist slova do NP movi prochitavshi ne bilshe nizh tri biti z vidpovidnogo dovedennya 20012012 de Hristos Papadimitriu de i Eva Tardosh za zakladennya osnov en 2009 2002 20012013 Den Boneh and za bagatostoronnij protokol Diffi Gellmana ta en v kriptografiyi 2003 20042014 fr and za optimalni algoritmi agregaciyi dlya promizhnogo programnogo zabezpechennya 2003 2015 Deniel Spilmen za nizku robit z praktichno linijnih rozv yazuvachiv Laplasa 2011 2013 20142016 Stephen Brookes and za vinahid en 2007 20072017 fr ta fr za doslidzhennya diferencijnoyi privatnosti 20062018 za vvedennya u rozglyad zadachi en 20092019 Irit Dinur za nove dovedennya PCP teoremi 2007Peremozhni praciBabai Laszlo Moran Shlomo 1988 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 arhiv originalu PDF za 6 lipnya 2011 procitovano 17 grudnya 2009 Goldwasser S Micali S Rackoff C 1989 PDF SIAM Journal on Computing Philadelphia Society for Industrial and Applied Mathematics 18 1 186 208 doi 10 1137 0218012 ISSN 1095 7111 arhiv originalu PDF za 27 veresnya 2011 procitovano 17 grudnya 2009 Hastad Johan 1989 Almost Optimal Lower Bounds for Small Depth Circuits u Micali Silvio red PDF Advances in Computing Research t 5 JAI Press s 6 20 ISBN 0892328967 arhiv originalu PDF za 22 lyutogo 2012 procitovano 17 grudnya 2009 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 Szelepcsenyi 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 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 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 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 Toda Seinosuke 1991 PDF SIAM Journal on Computing Philadelphia Society for Industrial and Applied Mathematics 20 5 865 877 doi 10 1137 0220053 ISSN 1095 7111 arhiv originalu PDF za 21 lyutogo 2007 procitovano 17 grudnya 2009 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 nedostupne posilannya z kvitnya 2019 Vardi Moshe Y Wolper Pierre 1994 PDF Information and Computation Boston MA Academic Press 115 1 1 37 doi 10 1006 inco 1994 1092 ISSN 0890 5401 arhiv originalu PDF za 25 serpnya 2011 procitovano 17 grudnya 2009 Feige Uriel Goldwasser Shafi Lovasz 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 Arora Sanjeev Safra Shmuel 1998 PDF Journal of the ACM ACM 45 1 70 122 doi 10 1145 273865 273901 ISSN 0004 5411 arhiv originalu PDF za 10 chervnya 2011 procitovano 17 grudnya 2009 Arora Sanjeev Lund Carsten Motwani Rajeev Sudan Madhu Szegedy Mario 1998 PDF Journal of the ACM ACM 45 3 501 555 doi 10 1145 278298 278306 ISSN 0004 5411 arhiv originalu PDF za 10 chervnya 2011 procitovano 17 grudnya 2009 Senizergues Geraud 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 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 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 Godel prize lecture 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 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 Agrawal M Kayal N Saxena N 2004 PDF Annals of Mathematics 160 781 793 doi 10 4007 annals 2004 160 781 ISSN 0003 486X arhiv originalu PDF za 7 chervnya 2011 procitovano 17 grudnya 2009 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 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 nedostupne posilannya z kvitnya 2019 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 nedostupne posilannya z kvitnya 2019 Reingold Omer 2008 J ACM ACM 55 4 1 24 ISSN 0004 5411 arhiv originalu za 12 chervnya 2011 procitovano 17 grudnya 2009 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 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 Hastad Johan 2001 Some optimal inapproximability results Journal of the ACM ACM 48 4 798 859 doi 10 1145 502090 502098 ISSN 0004 5411 Koutsoupias Elias Papadimitriou Christos 2009 Worst case equilibria Computer Science Review 3 2 65 69 doi 10 1016 j cosrev 2009 04 003 Roughgarden Tim Tardos Eva 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 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 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 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 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 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 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 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 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 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 Dwork Cynthia McSherry Frank Nissim Kobbi Smith Adam 2006 Halevi Shai Rabin Tal red Calibrating Noise to Sensitivity in Private Data Analysis Theory of Cryptography TCC Lecture Notes in Computer Science T 3876 Springer Verlag s 265 284 doi 10 1007 11681878 14 ISBN 978 3 540 32731 8 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 Dinur Irit 2007 The PCP theorem by gap amplification Journal of the ACM 54 3 Primitki 16 travnya 2012 Arhiv originalu za 18 July 2013 Procitovano 16 travnya 2012 ACM Group Presents Godel Prize for Advances in Cryptography Three Computer Scientists Cited for Innovations that Improve Security 2013 06 01 u 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 Godel Prize announcement 2017 12 09 u Wayback Machine by Association for Computing Machinery 2017 Godel Prize European Association for Theoretical Computer Science EATCS Procitovano 29 bereznya 2017 2018 Godel Prize citation 2019 Godel Prize citation PosilannyaOficijnij sajt zi spiskom laureativ

Дата публікації:
Топ