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
Країна  США
Тип наукова нагородаd і інформаційний списокd
На честь: Курт Гедель
Нагородження
Засновано: 1992
Нагороджені:
Категорія:Лауреати премії Геделя (12)
Черговість
 Премія Геделя у Вікісховищі

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

Лауреати Редагувати

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

1999

2011 Йохан Хастад за покращення PCP-теореми за допомогою нових імовірнісних верифікаторів, що дозволяють перевірити належність слова до NP-мови, прочитавши не більше ніж три біти з відповідного доведення 2001
2012 Elias Koutsoupias[de], Христос Пападімітріу, Noam Nisan, Amir Ronen[de], Tim Roughgarden і Ева Тардош за закладення основ алгоритмічної теорії ігор[en] 2009, 2002, 2001
2013 Ден Бонех, Matthew K. Franklin, and Antoine Joux за багатосторонній протокол Діффі-Геллмана та схему Боєна-Франкліна[en] в криптографії 2003,

2004

2014 Ronald Fagin, Amnon Lotem[fr], and Moni Naor за оптимальні алгоритми агрегації для проміжного програмного забезпечення 2003,
2015 Daniel Spielman, Shanghua Teng за низку робіт з практично-лінійних розв'язувачів Лапласа

2011 2013 2014

2016 Stephen Brookes and Peter W. O'Hearn за винахід Паралельної логіки розділення[en] 2007, 2007
2017 Cynthia Dwork, Frank McSherry[fr], Kobbi Nissim, та Adam D. Smith[fr] за дослідження диференційної приватності 2006
2018 Oded Regev за введення у розгляд задачи навчання з помилками[en] 2009
2019 Іріт Дінур за нове доведення PCP-теореми 2007

Переможні праці Редагувати

  1. Babai, László; Moran, Shlomo (1988). . 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. Архів оригіналу за 6 липня 2011. Процитовано 17 грудня 2009. 
  2. Goldwasser, S.; Micali, S.; Rackoff, C. (1989). . SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 18 (1): 186–208. ISSN 1095-7111. doi:10.1137/0218012. Архів оригіналу за 27 вересня 2011. Процитовано 17 грудня 2009. 
  3. Håstad, Johan (1989). . У 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). . SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics) 20 (5): 865–877. ISSN 1095-7111. doi:10.1137/0220053. Архів оригіналу за 21 лютого 2007. Процитовано 17 грудня 2009. 
  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). . 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). . 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). . 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). . 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). . 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. 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). 

Примітки Редагувати

  1. . 16 травня 2012. Архів оригіналу за 18 липня 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, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
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 Gedelyaangl Godel PrizeKrayina SShATip naukova nagorodad i informacijnij spisokdNa chest Kurt GedelNagorodzhennyaZasnovano 1992Nagorodzheni Kategoriya Laureati premiyi Gedelya 12 Chergovist Premiya Gedelya u VikishovishiPremiya 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 Zmist 1 Laureati 2 Peremozhni praci 3 Primitki 4 PosilannyaLaureati Redaguvati nbsp Kurt Gedel 1925 Rik Imena Za sho Rik publikaciyi1993 Laslo Babaj Shafi Goldvasser Silvio Mikali Shlomo Moran ta Charlz Rekof za rozrobku interaktivnih sistem dovedennya 1988 pracya 1 1989 pracya 2 1994 Johan Hostad za eksponentnu nizhnyu mezhu rozmiru logichnih cikliv z konstantnoyu glibinoyu dlya funkciyi parnosti 1989 pracya 3 1995 Nil Immerman ta Robert Selepcheni za teoremu Immermana Selepcheni stosovno nedeterminovanoyi prostorovoyi skladnosti 1988 pracya 4 1988 pracya 5 1996 Mark Dzherum ta Elister Sinkler za robotu nad lancyugami Markova i aproksimaciyeyu permanenta 1989 pracya 6 1989 pracya 7 1997 Dzhozef Galpern ta Joram Moses za viznachennya formalnogo zapisu znan u rozpodilenih seredovishah 1990 pracya 8 1998 Seinosuke Toda za teoremu Toda yaka pokazala zv yazok mizh obchislenimi rozv yazkami PP i cherguvannyam kvantoriv PH 1991 pracya 9 1999 Piter Shor za algoritm Shora dlya faktorizaciyi chisel za polinomialnij chas na kvantovomu komp yuteri 1997 pracya 10 2000 Moshe Vardi ta P yer Volper za robotu nad perevirkoyu modelej iz skinchennimi avtomatami 1994 pracya 11 2001 Sendzhev Arora Uriel Fejge Shafi Goldvasser Larsten Lund Laslo Lovas Radzhiv Motvani Shmuel Safra Madhu Sudan ta Mario Segedi za PCP teoremu ta yiyi zastosuvannya do skladnosti aproksimaciyi 1996 pracya 12 1998 pracya 13 1998 pracya 14 2002 Zhero Senizerg za dovedennya togo sho ekvivalentnist determinovanih stekovih avtomativ ye rozv yazuvanoyu 2001 pracya 15 2003 Jouv Fruend ta Robert Shapiro za algoritm AdaBoost 1997 pracya 16 2004 Moris Gerligu Majkl Saks Nir Shavit ta Fotios Zagaroglou za zastosuvannya topologiyi do teoriyi rozpodilenih obchislen 1999 pracya 17 2000 pracya 18 2005 Noga Alon Jossi Matias ta Mario Szegedy za yihnij fundamentalnij vnesok do potokovih algoritmiv 1999 pracya 19 2006 Manindra Agraval Niradzh Kayal Nitin Saksena za test prostoti AKS 2004 pracya 20 2007 Oleksandr Razborov Stiven Redik za prirodni dovedennya 1997 pracya 21 2008 Shang Hua Teng Deniel Spilmen za zgladzhenij analiz algoritmiv 2004 pracya 22 2009 Omer Reingold Salil Vadgen Avi Vigderson za zigzagovij dobutok grafiv ta nenapryamlenu zv yaznist u logarifmichnomu prostori 2002 pracya 23 2008 pracya 24 2010 Sendzhev Arora Dzhozef Mitchel za yihnye odnochasne vidkrittya polinomialnoyi aproksimacijnoyi shemi dlya evklidovoyi zadachi komivoyazhera ETSP 1998 pracya 25 1999 pracya 26 2011 Johan Hastad 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 2001 pracya 27 2012 Elias Koutsoupias de Hristos Papadimitriu Noam Nisan Amir Ronen de Tim Roughgarden i Eva Tardosh za zakladennya osnov algoritmichnoyi teoriyi igor en 1 2009 pracya 28 2002 pracya 29 2001 pracya 30 2013 Den Boneh Matthew K Franklin and Antoine Joux za bagatostoronnij protokol Diffi Gellmana ta shemu Boyena Franklina en v kriptografiyi 2 2003 pracya 31 2004 pracya 32 2014 Ronald Fagin Amnon Lotem fr and Moni Naor za optimalni algoritmi agregaciyi dlya promizhnogo programnogo zabezpechennya 3 2003 pracya 33 2015 Daniel Spielman Shanghua Teng za nizku robit z praktichno linijnih rozv yazuvachiv Laplasa 4 2011 pracya 34 2013 pracya 35 2014 pracya 36 2016 Stephen Brookes and Peter W O Hearn za vinahid Paralelnoyi logiki rozdilennya en 2007 pracya 37 2007 pracya 38 2017 5 Cynthia Dwork Frank McSherry fr Kobbi Nissim ta Adam D Smith fr za doslidzhennya diferencijnoyi privatnosti 2006 pracya 39 2018 6 Oded Regev za vvedennya u rozglyad zadachi navchannya z pomilkami en 2009 pracya 40 2019 7 Irit Dinur za nove dovedennya PCP teoremi 2007 pracya 41 Peremozhni praci Redaguvati Babai Laszlo 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 Arhiv originalu za 6 lipnya 2011 Procitovano 17 grudnya 2009 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 Arhiv originalu za 27 veresnya 2011 Procitovano 17 grudnya 2009 Hastad Johan 1989 Almost Optimal Lower Bounds for Small Depth Circuits U Micali Silvio Randomness and Computation Advances in Computing Research 5 JAI Press s 6 20 ISBN 0892328967 Arhiv originalu za 22 lyutogo 2012 Procitovano 17 grudnya 2009 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 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 ISSN 0890 5401 doi 10 1016 0890 5401 89 90067 9 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 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 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 Arhiv originalu 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 SIAM Journal on Computing Philadelphia Society for Industrial and Applied Mathematics 26 5 1484 1509 ISSN 1095 7111 doi 10 1137 S0097539795293172 nedostupne posilannya z kvitnya 2019 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 Arhiv originalu 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 Journal of the ACM ACM 43 2 268 292 ISSN 0004 5411 doi 10 1145 226643 226652 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 Arhiv originalu za 10 chervnya 2011 Procitovano 17 grudnya 2009 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 Arhiv originalu 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 ISSN 0304 3975 doi 10 1016 S0304 3975 00 00285 1 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 Herlihy Maurice Shavit Nir 1999 The topological structure of asynchronous computation 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 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 PRIMES is in P Annals of Mathematics 160 781 793 ISSN 0003 486X doi 10 4007 annals 2004 160 781 Arhiv originalu 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 ISSN 0022 0000 doi 10 1006 jcss 1997 1494 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 nedostupne posilannya z kvitnya 2019 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 nedostupne posilannya z kvitnya 2019 Reingold Omer 2008 Undirected connectivity in log space 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 ISSN 0004 5411 doi 10 1145 290179 290180 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 Hastad Johan 2001 Some optimal inapproximability results Journal of the ACM ACM 48 4 798 859 ISSN 0004 5411 doi 10 1145 502090 502098 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 doi 10 1145 506147 506153 Proignorovano nevidomij parametr citeseerx dovidka Nisan Noam Ronen Amir 2001 Algorithmic Mechanism Design Games and Economic Behavior 35 1 2 166 196 doi 10 1006 game 1999 0790 Proignorovano nevidomij parametr citeseerx dovidka 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 Proignorovano nevidomij parametr citeseerx dovidka 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 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 ISSN 0097 5397 arXiv 0808 4134 doi 10 1137 08074489X 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 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 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 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 Dwork Cynthia McSherry Frank Nissim Kobbi Smith Adam 2006 U Halevi Shai Rabin Tal Calibrating Noise to Sensitivity in Private Data Analysis Theory of Cryptography TCC Lecture Notes in Computer Science 3876 Springer Verlag s 265 284 ISBN 978 3 540 32731 8 doi 10 1007 11681878 14 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 Proignorovano nevidomij parametr citeseerx dovidka Dinur Irit 2007 The PCP theorem by gap amplification Journal of the ACM 54 3 Primitki Redaguvati Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory 16 travnya 2012 Arhiv originalu za 18 lipnya 2013 Procitovano 16 travnya 2012 ACM Group Presents Godel Prize for Advances in Cryptography Three Computer Scientists Cited for Innovations that Improve Security Arhivovano 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 Arhivovano 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 Posilannya RedaguvatiOficijnij sajt zi spiskom laureativ Otrimano z https uk wikipedia org w index php title Premiya Gedelya amp oldid 40137867