괴델상

위키백과, 우리 모두의 백과사전.

괴델상(Gödel Prize)은 쿠르트 괴델을 기리기 위해 만들었으며 이론 컴퓨터 과학 부문에서 특출난 논문을 발표한 사람에게 주는 상이다. 이론 컴퓨터 과학 유럽 연합(EATCS)(en)과 ACM SIGACT가 공동으로 수여한다. 이론 컴퓨터 과학에 대한 괴델과의 연관을 말하자면, 그는 1956년 존 폰 노이만에게 편지를 썼는데 특정 NP-완전 문제가 제곱, 혹은 선형의 시간 내에 풀릴 수 있는 지에 대해 물어봤으며 그때 처음으로 P-NP 문제를 언급한 사람이었다.[1]

괴델상은 1993년부터 수여되기 시작했다. 수여식은 STOC(컴퓨터 이론 ACM 심포지엄, 북미의 주요 이론 컴퓨터 과학 학회 중 하나)과 ICALP(en)(International Colloquium on Automata, Languages and Programming, 유럽의 주요 이론 컴퓨터 과학 학회 중 하나) 중 한 군데에서 열린다. 상을 받을 자격이 되려면, (이전에는 최근 7년 이었다.) 최근 14년 내에 학술지에 게재된 논문이어야 한다. 괴델상은 5000 미국 달러를 포함하고 있다.[2]

위원회 중 여섯 명이 수상자를 지목한다. EATCS 연합장과 SIGACT 연합장이 3년의 기간을 두고 각각의 위원회에서 3명씩 임명한다. EATCS와 SIGACT의 대표는 번갈아 가면서 위원회의 위원장을 맡는다.

수상자[편집]

연도 이름 노트 논문 게재 연도
1993 라슬로 버버이(László Babai), 샤피 골드바서(Shafi Goldwasser), 실비오 미칼리(Silvio Micali), 슐로모 모란(Shlomo Moran), 찰스 래코프(Charles Rackoff) for the development of interactive proof systems 1988,[paper 1] 1989[paper 2]
1994 요한 호스타드(Johan Håstad) the size of constant-depth Boolean circuits (for the parity function). 1989[paper 3]
1995 닐 이머만, 로베르트 셀렙체니(Róbert Szelepcsényi) for the Immerman–Szelepcsényi theorem regarding nondeterministic space complexity 1988,[paper 4] 1988[paper 5]
1996 마크 제럼(Mark Jerrum), 앨리스터 싱클레어(Alistair Sinclair) permanent of a matrix 1989,[paper 6] 1989[paper 7]
1997 조지프 핼펀(Joseph Halpern), 요람 모세스(Yoram Moses) for defining a formal notion of "knowledge" in distributed environments 1990[paper 8]
1998 도다 세이노스케(Seinosuke Toda) PP) and alternation of quantifiers (PH (complexity)PH) 1991[paper 9]
1999 피터 쇼어(Peter Shor) factoring numbers in polynomial time on a quantum computer 1997[paper 10]
2000 모셰 Y. 바르디(Moshe Y. Vardi), 피에르 월페르(Pierre Wolper) for work on temporal logic with finite automata 1994[paper 11]
2001 산지브 아로라(Sanjeev Arora), 우리엘 파이게(Uriel Feige), 샤피 골드바서(Shafi Goldwasser), 카르스텐 룬드(Carsten Lund), 라슬로 로바시(László Lovász), 란지브 모트와니(Rajeev Motwani), 슈무엘 사프라(Shmuel Safra), 마두 수단(Madhu Sudan), 마리오 셰게디(Mario Szegedy) for the PCP theorem and its applications to hardness of approximation 1996,[paper 12] 1998,[paper 13] 1998[paper 14]
2002 제로 세니제르그(Géraud Sénizergues) deterministic pushdown automata is (Decidability (logic))decidable 2001[paper 15]
2003 요아브 프로인드(Yoav Freund), 로버트 셔파이어(Robert Schapire) for the AdaBoost algorithm in machine learning 1997[paper 16]
2004 모리스 헐리히(Maurice Herlihy), 마이클 색스(Michael Saks), 니르 샤비트(Nir Shavit), 포티오스 자하로을루(Fotios Zaharoglou) for applications of topology to the theory of distributed computing 1999,[paper 17] 2000[paper 18]
2005 노가 알론(Noga Alon), 요시 마티아스(Yossi Matias), 마리오 셰게디(Mario Szegedy) for their foundational contribution to streaming algorithms 1999[paper 19]
2006 마닌드라 아그라왈(Manindra Agrawal), 니라이 카얄(Neeraj Kayal), 니틴 삭세나(Nitin Saxena) for the AKS primality test 2004[paper 20]
2007 알렉산드르 라즈보로프(Alexander Razborov), 스티븐 루디시(Steven Rudich) for natural proofs 1997[paper 21]
2008 대니얼 스필먼(Daniel Spielman), 텅상화(Shanghua Teng) for smoothed analysis of algorithms 2004[paper 22]
2009 오메르 레인골드(Omer Reingold), 살릴 바단(Salil Vadhan), 아비 위그데르손(Avi Wigderson) graphs and USTCON(undirected connectivity) in log space 2002,[paper 23] 2008[paper 24]
2010 산지브 아로라(Sanjeev Arora), 조지프 S. B. 미첼(Joseph S. B. Mitchell) for their concurrent discovery of a polynomial-time approximation scheme (PTAS) for the Euclidean Travelling Salesman Problem (ETSP) 1998,[paper 25]

1999[paper 26]

2011 요한 호스타드(Johan Håstad) for proving optimal inapproximability result for various combinatorial problems 2001[paper 27]
2012 엘리아스 쿠추피아스(Elias Koutsoupias), 흐리스토스 파파디미트리우(Christos Papadimitriou), 노암 니산(Noam Nisan), 아미르 로넨(Amir Ronen), 팀 러프가든(Tim Roughgarden), 터르도시 에버(Éva Tardos) for laying the foundations of algorithmic game theory[3] 2009,[paper 28] 2002,[paper 29] 2001[paper 30]
2013 댄 보네이(Dan Boneh), 매슈 K. 프랭클린(Matthew K. Franklin), 앙투안 주(Antoine Joux) for multi-party Diffie–Hellman key exchange and the Boneh–Franklin scheme in cryptography[4] 2003,[paper 31]

2004[paper 32]

2014 로널드 페이긴(Ronald Fagin), 암논 로템(Amnon Lotem), 모니 나오르(Moni Naor) for Optimal Aggregation Algorithms for Middleware[5] 2003,[paper 33]
2015 대니얼 스필먼(Daniel Spielman), 텅상화(Shanghua Teng) for their series of papers on nearly-linear-time Laplacian solvers[6]

2011[paper 34] 2013[paper 35] 2014[paper 36]

2016 스티븐 브룩스(Stephen Brookes), 피터 W. 오헌(Peter W. O'Hearn) Concurrent Separation Logic 2007[paper 37], 2007[paper 38]
2017[2] 신시아 드워크(Cynthia Dwork), 프랭크 맥셰리(Frank McSherry), 코비 니심(Kobbi Nissim), 애덤 D. 스미스(Adam D. Smith) for the invention of differential privacy 2006[paper 39]
2018[7] 오데드 레게브(Oded Regev) for introducing the Learning with errors problem 2009[paper 40]
2019[8] 이리트 디누르(Irit Dinur) for her new proof of the PCP theorem by gap amplification 2007[paper 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》 36 (2): 254–276, doi:10.1016/0022-0000(88)90028-1, ISSN 0022-0000, 2011년 7월 6일에 원본 문서 (PDF)에서 보존된 문서, 2020년 3월 10일에 확인함 
  2. ↑ Goldwasser, S.; Micali, S.; Rackoff, C. (1989), “The knowledge complexity of interactive proof systems” (PDF), 《SIAM Journal on Computing》 18 (1): 186–208, CiteSeerX 10.1.1.397.4002, doi:10.1137/0218012, ISSN 1095-7111, 2011년 9월 27일에 원본 문서 (PDF)에서 보존된 문서, 2020년 3월 10일에 확인함 
  3. ↑ Håstad, Johan (1989), 〈Almost Optimal Lower Bounds for Small Depth Circuits〉 (PDF), Micali, Silvio, 《Randomness and Computation》, Advances in Computing Research 5, JAI Press, 6–20쪽, ISBN 978-0-89232-896-3, 2012년 2월 22일에 원본 문서 (PDF)에서 보존된 문서 
  4. ↑ Immerman, Neil (1988), “Nondeterministic space is closed under complementation” (PDF), 《SIAM Journal on Computing》 17 (5): 935–938, CiteSeerX 10.1.1.54.5941, doi:10.1137/0217058, ISSN 1095-7111 
  5. ↑ Szelepcsényi, R. (1988), “The method of forced enumeration for nondeterministic automata” (PDF), 《Acta Informatica》 26 (3): 279–284, doi:10.1007/BF00299636, hdl:10338.dmlcz/120489 
  6. ↑ Sinclair, A.; Jerrum, M. (1989), “Approximate counting, uniform generation and rapidly mixing Markov chains”, 《Information and Computation》 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》 18 (6): 1149–1178, CiteSeerX 10.1.1.431.4190, doi:10.1137/0218077, ISSN 1095-7111 
  8. ↑ Halpern, Joseph; Moses, Yoram (1990), “Knowledge and common knowledge in a distributed environment” (PDF), 《Journal of the ACM》 37 (3): 549–587, arXiv:cs/0006009, doi:10.1145/79147.79161 
  9. ↑ Toda, Seinosuke (1991), “PP is as hard as the polynomial-time hierarchy” (PDF), 《SIAM Journal on Computing》 20 (5): 865–877, CiteSeerX 10.1.1.121.1246, doi:10.1137/0220053, ISSN 1095-7111, 2016년 3월 3일에 원본 문서 (PDF)에서 보존된 문서, 2020년 3월 10일에 확인함 
  10. ↑ Shor, Peter W. (1997), “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer” (PDF), 《SIAM Journal on Computing》 26 (5): 1484–1509, arXiv:quant-ph/9508027, doi:10.1137/S0097539795293172, ISSN 1095-7111 [깨진 링크]
  11. ↑ Vardi, Moshe Y.; Wolper, Pierre (1994), “Reasoning about infinite computations” (PDF), 《Information and Computation》 115 (1): 1–37, doi:10.1006/inco.1994.1092, ISSN 0890-5401, 2011년 8월 25일에 원본 문서 (PDF)에서 보존된 문서 
  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》 43 (2): 268–292, doi:10.1145/226643.226652, ISSN 0004-5411 
  13. ↑ Arora, Sanjeev; Safra, Shmuel (1998), “Probabilistic checking of proofs: a new characterization of NP” (PDF), 《Journal of the ACM》 45 (1): 70–122, doi:10.1145/273865.273901, ISSN 0004-5411, 2011년 6월 10일에 원본 문서 (PDF)에서 보존된 문서 
  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》 45 (3): 501–555, CiteSeerX 10.1.1.145.4652, doi:10.1145/278298.278306, ISSN 0004-5411, 2011년 6월 10일에 원본 문서 (PDF)에서 보존된 문서 
  15. ↑ Sénizergues, Géraud (2001), “L(A) = L(B)? decidability results from complete formal systems”, 《Theor. Comput. Sci.》 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》 55 (1): 119–139, doi:10.1006/jcss.1997.1504, ISSN 1090-2724 
  17. ↑ Herlihy, Maurice; Shavit, Nir (1999), “The topological structure of asynchronous computability” (PDF), 《Journal of the ACM》 46 (6): 858–923, CiteSeerX 10.1.1.78.1455, 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 (2): 781–793, doi:10.4007/annals.2004.160.781, ISSN 0003-486X, 2011년 6월 7일에 원본 문서 (PDF)에서 보존된 문서 
  21. ↑ Razborov, Alexander A.; Rudich, Steven (1997), “Natural proofs”, 《Journal of Computer and System Sciences》 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》 51 (3): 385–463, arXiv:math/0212413, doi:10.1145/990308.990310, ISSN 0004-5411 [깨진 링크]
  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, CiteSeerX 10.1.1.236.8669, doi:10.2307/3062153, ISSN 0003-486X, JSTOR 3062153, MR 1888797 [깨진 링크]
  24. ↑ Reingold, Omer (2008), “Undirected connectivity in log-space”, 《J. ACM》 55 (4): 1–24, doi:10.1145/1391289.1391291, ISSN 0004-5411, 2011년 6월 12일에 원본 문서에서 보존된 문서, 2020년 3월 10일에 확인함 
  25. ↑ Arora, Sanjeev (1998), “Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems”, 《Journal of the ACM》 45 (5): 753–782, CiteSeerX 10.1.1.23.6765, 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》 28 (4): 1298–1309, doi:10.1137/S0097539796309764, ISSN 1095-7111 
  27. ↑ Håstad, Johan (2001), “Some optimal inapproximability results” (PDF), 《Journal of the ACM》 48 (4): 798–859, CiteSeerX 10.1.1.638.2808, 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). 《Calibrating Noise to Sensitivity in Private Data Analysis》. Theory of Cryptography (TCC). Lecture Notes in Computer Science. Springer-Verlag. 265–284쪽. doi:10.1007/11681878_14. ISBN 978-3-540-32731-8.  이름 목록에서 |이름1=이(가) 있지만 |성1=이(가) 없음 (도움말)
  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): 12–es. doi:10.1145/1236457.1236459. 

같이 보기[편집]

각주[편집]

  1. ↑ “The Gödel Letter”. 2009년 2월 12일. 
  2. ↑ 가 나 “2017 Gödel Prize”. 《European Association for Theoretical Computer Science》. EATCS. 2017년 3월 29일에 확인함. 
  3. ↑ “Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory”. 2012년 5월 16일. 2013년 7월 18일에 원본 문서에서 보존된 문서. 2012년 5월 16일에 확인함. 
  4. ↑ ACM Group Presents Gödel Prize for Advances in Cryptography: Three Computer Scientists Cited for Innovations that Improve Security 보관됨 2013-06-01 - 웨이백 머신, Association for Computing Machinery, May 29, 2013.
  5. ↑ Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources, Association for Computing Machinery, April 30, 2014.
  6. ↑ 2015 Gödel Prize announcement 보관됨 2017-12-09 - 웨이백 머신 by Association for Computing Machinery.
  7. ↑ “2018 Gödel Prize citation”. 
  8. ↑ “2019 Gödel Prize citation”. 

참고[편집]

원본 주소 "https://ko.wikipedia.org/w/index.php?title=괴델상&oldid=36793006"