Loading article…
アレクサンダー・ラズボロフ | |
|---|---|
 オーバーヴォルファッハのラズボロフ、2024 | |
| 生まれる | 1963年2月16日 |
| 国籍 | アメリカ人、ロシア人 |
| 母校 | モスクワ国立大学 |
| 知られている | 群論、コンピュータサイエンスにおける論理、理論コンピュータサイエンス |
| 受賞歴 |
|
| 科学者としてのキャリア | |
| フィールド | 数学者 |
| 機関 | シカゴ大学、ステクロフ数学研究所、シカゴ豊田工業大学 |
| 博士課程の指導教員 | セルゲイ・アディアン |
アレクサンドル・アレクサンドロヴィチ・ラズボロフ（ロシア語: Алекса́ндр Алекса́ндрович Разбо́ров 、1963年2月16日生まれ）は、サーシャ・ラズボロフとしても知られ、ソビエトおよびロシアの数学者および計算理論家です。彼はシカゴ大学のアンドリュー・マクリーシュ特別教授です。
研究
スティーブン・ルディッチとの共同研究で最もよく知られている研究で、彼は自然証明の概念を導入しました。これは、計算複雑性の基本的な下限を証明するために使用される戦略のクラスです。特に、ラズボロフとルディッチは、ある種の一方向性関数が存在するという仮定の下では、そのような証明ではP = NP問題を解決できないため、この問題を解決するには新しい技術が必要になることを示しました。
受賞歴
- ネヴァンリンナ賞（1990年）いくつかの重要なアルゴリズム問題のブール回路の 下限値を証明する「近似法」の導入に対して[1]
- エルデシュ講師、エルサレム・ヘブライ大学、1998年。
- ロシア科学アカデミー通信会員（2000年）[2] [3]
- 論文「自然な証明」によりゲーデル賞（2007年、スティーブン・ルディッチと共同受賞） 。[4] [5]
- デイビッド・P・ロビンズ賞は、論文「グラフの三角形の最小密度について」（組合せ論、確率、計算 17 (2008)、第 4 号、603 ～ 618 ページ）と、極限組合せ論の問題を解決するための新しい強力な方法であるフラグ代数の導入に対して授与されました。
- ゲーデル講師（2010年）による「命題証明の複雑性」と題した講義。[6]
- シカゴ大学コンピュータサイエンス学部のアンドリュー・マクレイシュ特別教授（2008年） 。
- アメリカ芸術科学アカデミー（AAAS）フェロー（2020年）。[7]
文献
- Razborov, AA (1985). 「いくつかのブール関数の単調複雑度の下限値」(PDF) .ソビエト数学 - Doklady . 31 : 354–357.
- Razborov, AA (1985 年 6 月)。 「論理パーマネントの単調複雑性の下限」。ソ連科学アカデミー数学ノート。37 (6): 485–493。doi :10.1007/BF01157687。S2CID 120875831 。
- Разборов、Александр Александрович (1987)。 О системах уравнений в свободной группе (PDF) (ロシア語)。Московский государственный университет。 （博士論文。32.56MB）
- Razborov, AA (1987 年 4 月)。「論理加算による完全基底上の制限付き深度回路のサイズの下限」。ソ連科学アカデミー数学ノート。41 (4): 333–338。doi : 10.1007 /BF01137685。S2CID 121744639 。
- Razborov, Alexander A. (1989 年 5 月)。「第 21 回 ACM コンピューティング理論シンポジウム議事録 - STOC '89」。第 21 回 ACM コンピューティング理論シンポジウム議事録。米国ワシントン州シアトル。pp . 167–176。doi: 10.1145 / 73007.73023。ISBN 0897913078。
- Razborov, AA (1990 年 12 月)。「接触整流回路の対称ブール関数の複雑さの下限」。ソ連科学アカデミー数学ノート。48 ( 6): 1226–1234。doi :10.1007/BF01240265。S2CID 120703863 。
- Razborov, Alexander A.; Rudich, Stephen (1994 年 5 月)。「第 26 回 ACM コンピューティング理論シンポジウム議事録 - STOC '94」。第26 回 ACM コンピューティング理論シンポジウム議事録。カナダ、ケベック州、モントリオール。pp. 204–213。doi :10.1145/195058.195134。ISBN 0897916638。
- Razborov, Alexander A. (1998 年 12 月). 「多項式計算の下限値」(PostScript) .計算複雑性. 7 (4): 291–324. CiteSeerX 10.1.1.19.2441 . doi :10.1007/s000370050013. S2CID 8130114.
- Razborov, Alexander A. (2003 年 1 月). 「命題証明の複雑さ」(PostScript) . Journal of the ACM . 50 (1): 80–82. doi :10.1145/602382.602406. S2CID 17351318. （JACM創立50周年記念調査論文）
参照
注記
- ^ 「国際数学連合：ロルフ・ネヴァンリンナ賞受賞者」。2007年12月17日時点のオリジナルよりアーカイブ。
- ^ “ロシア科学アカデミー: ラズボロフ・アレクサンドル・アレクサンドロヴィッチ: 一般情報: 歴史”.
- ^ 「Russian Genealogy Agencies Tree: R」（ロシア語）。2007年12月21日時点のオリジナルよりアーカイブ。2008年1月15日閲覧。
- ^ 「ACM-SIGACT 賞と賞品: 2007 ゲーデル賞」。
- ^ 「EATCS: Gödel Prize - 2007」。2007年12月1日時点のオリジナルよりアーカイブ。
- ^ “Gödel Lecturers – Association for Symbolic Logic”. 2021-11-08時点のオリジナルよりアーカイブ。2021-11-10閲覧。
- ^ 「AAASフェロー選出」(PDF)。アメリカ数学会の通知。
外部リンク
- 数学系譜プロジェクトの Alexander Razborov 氏。
- アレクサンダー・ラズボロフのホームページ。
- 全ロシア数学ポータル: 人物: ラズボロフ アレクサンダー アレクサンドロヴィチ。
- シカゴのトヨタ工業大学での経歴。
- シカゴ大学コンピュータサイエンス学部の履歴書。
- DBLP: アレクサンダー・A・ラズボロフ。
- アレクサンダー・ラズボロフの国際数学オリンピックでの成績
- AA ラズボロフの研究 – 1990 年に京都で開催された国際数学者会議の議事録に掲載されたLászló Lovászによる論文。