Loading article…
ミクロス・アイタイ（1946年7月2日生まれ）は、アメリカ合衆国IBMアルマデン研究所のコンピュータ科学者です。2003年に、古典的なソートネットワークアルゴリズム（J.コムロス、エンドレ・セメレディと共同開発）、指数関数的な下限、分岐プログラムの超線形時間空間トレードオフ、その他「ユニークで素晴らしい」成果など、この分野への数々の貢献によりクヌース賞を受賞しました。彼は米国科学アカデミーの会員です。[ 2 ]
アジタイの結果の一つは、 n 個の項目に対する鳩の巣原理の命題論理における証明の長さが、nの任意の多項式よりも速く増加するというものである。彼はまた、「2 階同値な任意の2 つの可算構造は同型でもある」という命題がZFCと矛盾せず、かつ ZFCとは独立していることを証明した。アジタイとセメレディは、セメレディの定理の高次元一般化への重要なステップであるコーナー定理を証明した。コムロスとセメレディと共に、ラムゼイ数R (3, t )の上限ct 2 /log tを証明した。コムロスとトゥスナディと共に、1984 年にAKT 最適マッチング定理を証明した。対応する下限は、キムによって1995 年にようやく証明され、その結果、彼はフルカーソン賞を受賞した。 Ajtai はChvátal、Newborn、Szemerédiと共に、n個の頂点とm個の辺を持つグラフ(m > 4 n )の任意の描画には、少なくともm 3 / 100 n 2 個の交差があるという交差数不等式を証明しました。 Ajtai とDwork は1997 年に格子ベースの公開鍵暗号システムを考案しました。 Ajtai は格子問題について広範な研究を行ってきました。 理論計算機科学における彼の数々の貢献により、彼は Knuth 賞を受賞しました。[ 1 ] IEEE は2025 年に、「計算複雑性の下限を確立し、格子ベースの暗号の基礎を築いた」功績により、 Ajtai にJohn von Neumann メダルを授与しました。[ 3 ]
アジタイは1976年にハンガリー科学アカデミーから科学候補の学位を授与された。[ 4 ] 1995年以来、彼はハンガリー科学アカデミーの外部会員である。
1998年、彼はベルリンで開催された国際数学者会議に招待講演者として参加した。[ 5 ] 2012年、彼はアメリカ科学振興協会のフェローに選出された。[ 6 ] 2021年、彼は米国科学アカデミーの会員に選出された。[ 7 ]
{{cite web}}: CS1 maint: タイトルとしてアーカイブされたコピー (リンク)新たに選出された会員とその選出時の所属は次のとおりです。... Ajtai, Miklós; IBM名誉研究員、IBMアルマデン研究センター、カリフォルニア州ロスガトス。