Loading article…
ラッセル・グラハム・インパグリアッツォ | |
|---|---|
 2016 年 7 月の DIMACS 暗号化ワークショップでの Russell Impagliazzo。 | |
| 母校 | ウェズリアン大学、カリフォルニア大学バークレー校 |
| 知られている | 計算複雑性理論における結果 |
| 科学者としてのキャリア | |
| 論文 | 確率アルゴリズムと暗号のための疑似乱数生成器 (1992) |
| 博士課程の指導教員 | マヌエル・ブルム |
| Webサイト | https://cseweb.ucsd.edu//~russell/ |
ラッセル・グラハム・インパグリアッツォ[1]は、カリフォルニア大学サンディエゴ校のコンピュータサイエンスの教授であり、計算複雑性理論を専門としています。[2]
教育
インパグリアッツォはウェズリアン大学で数学の学士号を取得しました。[3]彼は1992年にカリフォルニア大学バークレー校で博士号を取得しました。彼の指導教官はマヌエル・ブルムでした。[1] 彼は1989年にUCSDの教員となり、[4] 1989年から1991年までそこでポスドクを務めました。[3]
貢献
インパグリアッツォの複雑性理論への貢献には以下のものがあります。
- 任意の一方向性関数からの疑似乱数生成器の構築、[5]
- ヤオのXOR補題を「ハードコア集合」によって証明した[6]
- 鳩の巣原理の定数深さヒルベルト証明の指数的サイズ下限の証明、[7]
- 計算困難性と非ランダム化の関係に関する研究[8] [9] [10] [11]
- マルチソースシードレス抽出機の構築に関する研究。[12]
- 3-SATは変数の数に対して指数関数的時間未満で解くことはできないという指数時間仮説を述べており、 [13]この仮説はコンピュータサイエンスにおけるアルゴリズムの下限を推論するために使用されている。[14] [15]
複雑性理論の5つの世界
インパグリアッツォは、 P対NP問題を取り巻く世界の可能な状態を反映した計算複雑性理論の「5つの世界」を提唱したことでよく知られている。[16]
- アルゴリズミカ：P = NP;
- ヒューリスティック: P は NP ではありませんが、NP の問題は平均的には扱いやすいです。
- Pessiland: 平均的には難しい NP 問題はあるが、一方向関数は存在しない。
- Minicrypt: 一方向関数は存在しますが、公開鍵暗号化は存在しません。
- 暗号マニア: 公開鍵暗号が存在します。
私たちがどの世界に住んでいるのかを理解することは、複雑性理論と暗号学において依然として重要な動機となる問題です。[17]
受賞歴
Impagliazzo は以下の賞を受賞しました:
- 計算複雑性会議の最優秀論文賞[3]
- 2003年応用数学協会優秀論文賞[4]
- 2003年計算理論シンポジウム最優秀論文賞[4]
- 2004年に「ヒューリスティックス、証明の複雑さ、アルゴリズム技術」に関する研究でグッゲンハイムフェローに選出された[4]
参考文献
- ^ ab 「ラッセル・インパグリアッツォ - 数学系譜プロジェクト」。mathgenealogy.org 。2021年8月30日閲覧。
- ^ 「Russell Impagliazzo's」cseweb.ucsd.edu . 2021年8月30日閲覧。
- ^ abc 「Russell Impagliazzo | Simons Institute for the Theory of Computing」. simons.berkeley.edu . 2021年8月30日閲覧。
- ^ abcd 「教員プロフィール | ジェイコブス工学部」jacobsschool.ucsd.edu . 2021年8月30日閲覧。
- ^ HÅstad, Johan; Impagliazzo, Russell; Levin, Leonid A.; Luby, Michael (1999). 「任意の一方向関数からの疑似乱数ジェネレーター」(PDF) . SIAM Journal on Computing . 28 (4): 1364–1396. doi :10.1137/S0097539793244708. ISSN 0097-5397.
- ^ Impagliazzo, Russell (1995). 「やや難しい問題に対するハードコア分布」. Proceedings of IEEE 36th Annual Foundations of Computer Science . Proceedings of IEEE 36th Annual Foundations of Computer Science. pp. 538–545. doi :10.1109/SFCS.1995.492584. ISBN 0-8186-7183-1. 2021年8月30日閲覧。
- ^ Beame, Paul; Impagliazzo, Russell; Krajíček, Jan; Pitassi, Toniann; Pudlák, Pavel (1996). 「ヒルベルトの零点定理と命題証明の下限値」.ロンドン数学会紀要. s3-73 (1): 1–26. doi :10.1112/plms/s3-73.1.1. ISSN 1460-244X.
- ^ Kabanets, Valentine; Impagliazzo, Russell (2004-12-01). 「多項式アイデンティティテストの非ランダム化は回路の下限を証明することを意味する」.計算複雑性. 13 (1): 1–46. doi :10.1007/s00037-004-0182-6. ISSN 1420-8954. S2CID 12451799.
- ^ Impagliazzo, Russell; Wigderson, Avi (1997-05-04). 「E に指数回路が必要な場合は P = BPP」。第29 回 ACM 計算理論シンポジウム議事録 - STOC '97 。米国テキサス州エルパソ: Association for Computing Machinery。pp. 220–229。doi :10.1145/258533.258590。ISBN 978-0-89791-888-6. S2CID 18921599。
- ^ Impagliazzo, Russell (2003-04-28). 「ランダム性としての硬さ: 普遍的デランダム化の調査」. arXiv : cs/0304040 .
- ^ Carmosino, Marco L.; Impagliazzo, Russell; Kabanets, Valentine; Kolokolova, Antonina (2015). Garg, Naveen; Jansen, Klaus; Rao, Anup; Rolim, José DP (eds.). 「デランダム化と回路下限値のより緊密な関係」。近似、ランダム化、および組み合わせ最適化。アルゴリズムとテクニック (APPROX/RANDOM 2015) 。ライプニッツ国際情報科学会議 (LIPIcs) 。40。ダグシュトゥール、ドイツ: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 645–658。doi : 10.4230/LIPIcs.APPROX- RANDOM.2015.645。ISBN 978-3-939897-89-7。
- ^ Barak, B.; Impagliazzo, R.; Wigderson, A. (2004). 「少数の独立ソースを使用したランダム性の抽出」.第 45 回 IEEE コンピュータサイエンス基礎シンポジウム. pp. 384–393. doi :10.1109/FOCS.2004.29. ISBN 0-7695-2228-9. S2CID 7063583。
- ^ Impagliazzo, Russell; Paturi, Ramamohan (2001-03-01). 「k-SAT の複雑性について」. Journal of Computer and System Sciences . 62 (2): 367–375. doi : 10.1006/jcss.2000.1727 . ISSN 0022-0000.
- ^ ロクシュタノフ、ダニエル; マルクス、ダニエル; サウラブ、サケット (2011 年 10 月)。「指数時間仮説に基づく下限値」。EATCS紀要: 41–71。CiteSeerX 10.1.1.942.6217。
- ^ Williams, Virginia V. (2015). 簡単な問題の難しさ: 強い指数時間仮説などの一般的な推測に基づく難しさ(PDF)。第10回パラメータ化および厳密な計算に関する国際シンポジウム。pp. 17–29。doi : 10.4230/ LIPIcs.IPEC.2015.17。
- ^ インパグリアッツォ、ラッセル（1995 年 4 月 17 日）。「平均ケース複雑性に関する個人的な見解」。
- ^ Klarreich, Erica (2022年4月18日). 「私たちはどの計算宇宙に住んでいるのか?」Quanta .
外部リンク
- ラッセル・インパグリアッツォ
- UCSD ジェイコブス工学部教員プロフィール