「ゲーデル賞」の版間の差分

削除された内容追加された内容

インライン

2020年9月5日 (土) 05:14時点における版

ゲーデル賞 (Gödel Prize) は、理論計算機科学分野で優れた功績を残した人に、ACM（国際計算機学会）のアルゴリズムと計算量理論に関する部会とEATCS（ヨーロッパ理論コンピュータ学会）が贈る賞である。受賞者には賞金5,000ドルが贈られる。論理学者クルト・ゲーデルに由来する。計算機科学分野ではチューリング賞と並んで権威を持つ賞である。

受賞者一覧

Year	受賞者	授賞理由	論文発表年
1993	László Babai（英語版）, シャフィ・ゴールドワッサー, Silvio Micali, Shlomo Moran（英語版）, Charles Rackoff（英語版）	対話型証明システムの発明	1988,^{[論文 1]} 1989^{[論文 2]}
1994	Johan Håstad（英語版）	パリティ関数の定数深さの回路は、サイズの下界が指数関数となること	1989^{[論文 3]}
1995	Neil Immerman（英語版）, Róbert Szelepcsényi（英語版）	Immerman–Szelepcsényiの定理（英語版）	1988,^{[論文 4]} 1988^{[論文 5]}
1996	Mark Jerrum（英語版）, Alistair Sinclair（英語版）	マルコフ連鎖と行列のパーマネントの近似に対する業績	1989,^{[論文 6]} 1989^{[論文 7]}
1997	Joseph Halpern（英語版）, Yoram Moses（英語版）	分散環境における「知識」の形式概念の定義	1990^{[論文 8]}
1998	戸田誠之助	戸田の定理	1991^{[論文 9]}
1999	ピーター・ショア	ショアのアルゴリズム	1997^{[論文 10]}
2000	Moshe Y. Vardi（英語版）, Pierre Wolper（英語版）	有限オートマトンによる時相論理への業績	1994^{[論文 11]}
2001	Sanjeev Arora（英語版）, Uriel Feige（英語版）, シャフィ・ゴールドワッサー, Carsten Lund（英語版）, ラースロー・ロヴァース, Rajeev Motwani（英語版）, Shmuel Safra（英語版）, Madhu Sudan（英語版）, Mario Szegedy（英語版）	PCP定理（英語版）と近似の困難さへの応用	1996,^{[論文 12]} 1998,^{[論文 13]} 1998^{[論文 14]}
2002	Géraud Sénizergues（英語版）	決定性プッシュダウン・オートマトン（英語版）の等価性が決定可能であることの証明	2001^{[論文 15]}
2003	Yoav Freund（英語版）, Robert Schapire（英語版）	AdaBoost	1997^{[論文 16]}
2004	Maurice Herlihy（英語版）, Michael Saks（英語版）, Nir Shavit（英語版）, Fotios Zaharoglou（英語版）	トポロジーの分散コンピューティングへの応用	1999,^{[論文 17]} 2000^{[論文 18]}
2005	Noga Alon（英語版）, ヨシ・マティアス, Mario Szegedy（英語版）	ストリーミングアルゴリズム（英語版）に対する基本的な貢献	1999^{[論文 19]}
2006	マニンドラ・アグラワル, ニラジュ・カヤル, Nitin Saxena（英語版）	AKS素数判定法	2004^{[論文 20]}
2007	Alexander Razboroven（英語版）, Steven Rudich（英語版）	自然な証明	1997^{[論文 21]}
2008	Daniel Spielman（英語版）, Shanghua Teng（英語版）	アルゴリズムの平滑化解析（英語版）	2004^{[論文 22]}
2009	Omer Reingold（英語版）, Salil Vadhan（英語版）, Avi Wigderson（英語版）	グラフ理論におけるジグザグ積（英語版）およびUSTCONが対数領域で解けること	2002,^{[論文 23]} 2008^{[論文 24]}
2010	Sanjeev Arora（英語版）, Joseph S. B. Mitchell（英語版）	ユークリッド距離に基づく巡回セールスマン問題に対する多項式時間近似スキームの発見	1998,^{[論文 25]} 1999^{[論文 26]}
2011	Johan Håstad（英語版）	さまざまな組み合わせ問題に対する近似不可能性の証明	2001^{[論文 27]}
2012	Elias Koutsoupias（英語版）, クリストス・パパディミトリウ, Noam Nisan（英語版）, Amir Ronen（ドイツ語版）, Tim Roughgarden（英語版）, Éva Tardos（英語版）	アルゴリズム的ゲーム理論（英語版）の基礎を築く^[1]	2009,^{[論文 28]} 2002,^{[論文 29]} 2001^{[論文 30]}
2013	Dan Boneh（英語版）, Matthew K. Franklin（英語版）, Antoine Joux（英語版）	マルチパーティディフィー・ヘルマン鍵共有およびBoneh–Franklin scheme（英語版）^[2]	2003,^{[論文 31]} 2004^{[論文 32]}
2014	ロナルド・フェイギン, Amnon Lotem（フランス語版）, Moni Naor（英語版）	ミドルウェアのための最適な集約アルゴリズム^[3]	2003,^{[論文 33]}
2015	Daniel Spielman（英語版）, Shanghua Teng（英語版）	ほぼ線形時間のラプラシアンソルバーに関する一連の論文^[4]	2011^{[論文 34]}, 2013^{[論文 35]}, 2014^{[論文 36]}
2016	Stephen Brookes（ドイツ語版）, Peter O'Hearn（英語版）	Concurrent Separation Logic の発明	2007^{[論文 37]}, 2007^{[論文 38]}
2017^[5]	Cynthia Dwork（英語版）, Frank McSherry（フランス語版）, Kobbi Nissim（英語版）, Adam D. Smith（フランス語版）	differential privacy（英語版）の発明	2006^{[論文 39]}
2018^[6]	Oded Regev（英語版）	Learning with errors（英語版）問題の導入	2009^{[論文 40]}
2019^[7]	Irit Dinur（英語版）	PCP定理に対する新たな証明	2007^{[論文 41]}
2020^[8]	Robin Moser, Gábor Tardos（英語版）	Lovász Local Lemmaに対する構成的な証明	2010^{[論文 42]}

受賞論文

^ 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 36 (2): 254–276, doi:10.1016/0022-0000(88)90028-1, ISSN 0022-0000
^ Goldwasser, S.; Micali, S.; Rackoff, C. (1989), “The knowledge complexity of interactive proof systems”, SIAM Journal on Computing 18 (1): 186–208, doi:10.1137/0218012, ISSN 1095-7111
^ Håstad, Johan (1989), “Almost Optimal Lower Bounds for Small Depth Circuits”, in Micali, Silvio, Randomness and Computation, Advances in Computing Research, 5, JAI Press, pp. 6–20, ISBN 978-0-89232-896-3, オリジナルの2012-02-22時点におけるアーカイブ。
^ Immerman, Neil (1988), “Nondeterministic space is closed under complementation”, SIAM Journal on Computing 17 (5): 935–938, doi:10.1137/0217058, ISSN 1095-7111
^ Szelepcsényi, R. (1988), “The method of forced enumeration for nondeterministic automata”, Acta Informatica 26 (3): 279–284, doi:10.1007/BF00299636, hdl:10338.dmlcz/120489
^ 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
^ Jerrum, M.; Sinclair, Alistair (1989), “Approximating the permanent”, SIAM Journal on Computing 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, arXiv:cs/0006009, doi:10.1145/79147.79161
^ Toda, Seinosuke (1991), “PP is as hard as the polynomial-time hierarchy”, SIAM Journal on Computing 20 (5): 865–877, doi:10.1137/0220053, ISSN 1095-7111
^ Shor, Peter W. (1997), “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, SIAM Journal on Computing 26 (5): 1484–1509, arXiv:quant-ph/9508027, doi:10.1137/S0097539795293172, ISSN 1095-7111
^ Vardi, Moshe Y.; Wolper, Pierre (1994), “Reasoning about infinite computations”, Information and Computation 115 (1): 1–37, doi:10.1006/inco.1994.1092, ISSN 0890-5401, オリジナルの2011-08-25時点におけるアーカイブ。
^ Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (1996), “Interactive proofs and the hardness of approximating cliques”, Journal of the ACM 43 (2): 268–292, doi:10.1145/226643.226652, ISSN 0004-5411
^ Arora, Sanjeev; Safra, Shmuel (1998), “Probabilistic checking of proofs: a new characterization of NP”, Journal of the ACM 45 (1): 70–122, doi:10.1145/273865.273901, ISSN 0004-5411, オリジナルの2011-06-10時点におけるアーカイブ。
^ Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), “Proof verification and the hardness of approximation problems”, Journal of the ACM 45 (3): 501–555, doi:10.1145/278298.278306, ISSN 0004-5411, オリジナルの2011-06-10時点におけるアーカイブ。
^ 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
^ 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 55 (1): 119–139, doi:10.1006/jcss.1997.1504, ISSN 1090-2724
^ Herlihy, Maurice; Shavit, Nir (1999), “The topological structure of asynchronous computability”, Journal of the ACM 46 (6): 858–923, doi:10.1145/331524.331529 . Gödel 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 (2): 781–793, doi:10.4007/annals.2004.160.781, ISSN 0003-486X, オリジナルの2011-06-07時点におけるアーカイブ。
^ 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
^ Spielman, Daniel A.; Teng, Shang-Hua (2004), “Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time”, J. ACM 51 (3): 385–463, arXiv:math/0212413, doi:10.1145/990308.990310, ISSN 0004-5411
^ 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, doi:10.2307/3062153, ISSN 0003-486X, JSTOR 3062153, MR1888797, https://jstor.org/stable/3062153
^ Reingold, Omer (2008), “Undirected connectivity in log-space”, J. ACM 55 (4): 1–24, doi:10.1145/1391289.1391291, ISSN 0004-5411
^ Arora, Sanjeev (1998), “Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems”, Journal of the 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 28 (4): 1298–1309, doi:10.1137/S0097539796309764, ISSN 1095-7111
^ Håstad, Johan (2001), “Some optimal inapproximability results”, Journal of the 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, Éva (2002). “How bad is selfish routing?”. Journal of the ACM 49 (2): 236–259. doi:10.1145/506147.506153.
^ Nisan, Noam; Ronen, Amir (2001). “Algorithmic Mechanism Design”. Games and Economic Behavior 35 (1–2): 166–196. 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. doi:10.1137/S0097539701398521. MR2001745.
^ 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. MR2090557.
^ 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”. 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). Halevi, Shai; Rabin, Tal (eds.). Calibrating Noise to Sensitivity in Private Data Analysis. Theory of Cryptography (TCC). Lecture Notes in Computer Science. Vol. 3876. Springer-Verlag. pp. 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. doi:10.1145/1568318.1568324.
^ Dinur, Irit (2007). “The PCP theorem by gap amplification”. Journal of the ACM 54 (3): 12–es. doi:10.1145/1236457.1236459.
^ “A constructive proof of the general Lovász Local Lemma”. Journal of the ACM 57 (2). (2010). doi:10.1145/1667053. ISSN 00045411.

脚注

^ “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 Archived 2013-06-01 at the 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 Archived 2017-12-09 at the 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”. 2020年9月5日閲覧。
^ “2019 Gödel Prize citation”. 2020年9月5日閲覧。
^ “2020 Gödel Prize citation”. 2020年9月5日閲覧。

[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 36 (2): 254–276, doi:10.1016/0022-0000(88)90028-1, ISSN 0022-0000

[2] Goldwasser, S.; Micali, S.; Rackoff, C. (1989), “The knowledge complexity of interactive proof systems”, SIAM Journal on Computing 18 (1): 186–208, doi:10.1137/0218012, ISSN 1095-7111

[3] Håstad, Johan (1989), “Almost Optimal Lower Bounds for Small Depth Circuits”, in Micali, Silvio, Randomness and Computation, Advances in Computing Research, 5, JAI Press, pp. 6–20, ISBN 978-0-89232-896-3, オリジナルの2012-02-22時点におけるアーカイブ。

[4] Immerman, Neil (1988), “Nondeterministic space is closed under complementation”, SIAM Journal on Computing 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 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, 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, arXiv:cs/0006009, doi:10.1145/79147.79161

[9] Toda, Seinosuke (1991), “PP is as hard as the polynomial-time hierarchy”, SIAM Journal on Computing 20 (5): 865–877, doi:10.1137/0220053, ISSN 1095-7111

[10] Shor, Peter W. (1997), “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, 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”, Information and Computation 115 (1): 1–37, doi:10.1006/inco.1994.1092, ISSN 0890-5401, オリジナルの2011-08-25時点におけるアーカイブ。

[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 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”, Journal of the ACM 45 (1): 70–122, doi:10.1145/273865.273901, ISSN 0004-5411, オリジナルの2011-06-10時点におけるアーカイブ。

[14] Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), “Proof verification and the hardness of approximation problems”, Journal of the ACM 45 (3): 501–555, doi:10.1145/278298.278306, ISSN 0004-5411, オリジナルの2011-06-10時点におけるアーカイブ。

[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”, 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”, 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 (2): 781–793, doi:10.4007/annals.2004.160.781, ISSN 0003-486X, オリジナルの2011-06-07時点におけるアーカイブ。

[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”, 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”, Annals of Mathematics 155 (1): 157–187, doi:10.2307/3062153, ISSN 0003-486X, JSTOR 3062153, MR1888797, https://jstor.org/stable/3062153

[24] Reingold, Omer (2008), “Undirected connectivity in log-space”, J. ACM 55 (4): 1–24, doi:10.1145/1391289.1391291, ISSN 0004-5411

[25] Arora, Sanjeev (1998), “Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems”, Journal of the 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 28 (4): 1298–1309, doi:10.1137/S0097539796309764, ISSN 1095-7111

[27] Håstad, Johan (2001), “Some optimal inapproximability results”, Journal of the ACM 48 (4): 798–859, doi:10.1145/502090.502098, ISSN 0004-5411

[29] Koutsoupias, Elias; Papadimitriou, Christos (2009). “Worst-case equilibria”. Computer Science Review 3 (2): 65–69. doi:10.1016/j.cosrev.2009.04.003.

[30] Roughgarden, Tim; Tardos, Éva (2002). “How bad is selfish routing?”. Journal of the ACM 49 (2): 236–259. doi:10.1145/506147.506153.

[31] Nisan, Noam; Ronen, Amir (2001). “Algorithmic Mechanism Design”. Games and Economic Behavior 35 (1–2): 166–196. doi:10.1006/game.1999.0790.

[33] Boneh, Dan; Franklin, Matthew (2003). “Identity-based encryption from the Weil pairing”. SIAM Journal on Computing 32 (3): 586–615. doi:10.1137/S0097539701398521. MR2001745.

[34] 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. MR2090557.

[36] 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.

[SpielmanTeng2011-38] 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.

[SpielmanTeng2013-39] 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.

[SpielmanTeng2014-40] 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.

[41] 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.

[42] 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.

[44] Dwork, Cynthia; McSherry, Frank; Nissim, Kobbi; Smith, Adam (2006). Halevi, Shai; Rabin, Tal (eds.). Calibrating Noise to Sensitivity in Private Data Analysis. Theory of Cryptography (TCC). Lecture Notes in Computer Science. Vol. 3876. Springer-Verlag. pp. 265–284. doi:10.1007/11681878_14. ISBN 978-3-540-32731-8。

[Regev2009-46] 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.

[Dinur2007-48] Dinur, Irit (2007). “The PCP theorem by gap amplification”. Journal of the ACM 54 (3): 12–es. doi:10.1145/1236457.1236459.

[MoserTardos2010-50] “A constructive proof of the general Lovász Local Lemma”. Journal of the ACM 57 (2). (2010). doi:10.1145/1667053. ISSN 00045411.

[sigact-2012-28] “Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory”. (16 May 2012). オリジナルの18 July 2013時点におけるアーカイブ。 16 May 2012閲覧。

[32] ACM Group Presents Gödel Prize for Advances in Cryptography: Three Computer Scientists Cited for Innovations that Improve Security Archived 2013-06-01 at the Wayback Machine., Association for Computing Machinery, May 29, 2013.

[35] Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources, Association for Computing Machinery, April 30, 2014.

[37] 2015 Gödel Prize announcement Archived 2017-12-09 at the Wayback Machine. by Association for Computing Machinery.

[Godël2017-43] “2017 Gödel Prize”. European Association for Theoretical Computer Science. EATCS. 29 March 2017閲覧。

[Godël2018-45] “2018 Gödel Prize citation”. 2020年9月5日閲覧。

[Godël2019-47] “2019 Gödel Prize citation”. 2020年9月5日閲覧。

[Godël2020-49] “2020 Gödel Prize citation”. 2020年9月5日閲覧。

[論文 1]

[論文 2]

[論文 3]

[論文 4]

[論文 5]

[論文 6]

[論文 7]

[論文 8]

[論文 9]

[論文 10]

[論文 11]

[論文 12]

[論文 13]

[論文 14]

[論文 15]

[論文 16]

[論文 17]

[論文 18]

[論文 19]

[論文 20]

[論文 21]

[論文 22]

[論文 23]

[論文 24]

[論文 25]

[論文 26]

[論文 27]

[1]

[論文 28]

[論文 29]

[論文 30]

[2]

[論文 31]

[論文 32]

[3]

[論文 33]

[4]

[論文 34]

[論文 35]

[論文 36]

[論文 37]

[論文 38]

[5]

[論文 39]

[6]

[論文 40]

[7]

[論文 41]

[8]

[論文 42]